Sadece 2 sayfalık kağıtla Pekin Üniversitesi mezunları 30 yıldır bilgisayar sorununu çözdüler! Anlamak için sadece temel doğrusal cebire ihtiyaç vardır
İçbükey tapınaktan Bian Ce
Qubit Raporu | Genel Hesap QbitAI
Matematik dünyasında Goldbach'ın varsayımı ve Riemann'ın varsayımı gibi birçok varsayım vardır Bazı sorunlar, yüzlerce yıldır tüm insanlığı rahatsız etmektedir.
Bir gün birisi aniden dışarı fırlayıp şöyle dedi: "XX varsayımını ispatlamak için sadece birkaç sayfa kullandım." Herkes kesinlikle bu kişinin "sivil" olduğunu düşünecek.
Son zamanlarda Çinli bir matematikçi Huang Hao Bilgisayar teorisini 30 yıldır rahatsız eden bir varsayımı kanıtladığını ve yalnızca İki sayfa . Bu habere ilk bakışta birçok insanın ilk tepkisi şu olabilir: Yine bir "vizon" değil mi?
Ancak işler o kadar basit değil. Huang Haonun özgeçmişine baktığımızda, Pekin Üniversitesi Matematik Bölümünden mezun olduğunu ve 2012 yılında UCLAdan doktora derecesi aldığını göreceğiz. Kendisi şu anda Amerikada. Emory Üniversitesi Matematik ve Bilgisayar Bilimleri Bölümü'nde Yardımcı Doçent.
Huang Hao, sorunu gerçekten çözdü. Anlamak için sadece lisans bilgisi gerektiren iki sayfalık bir ispat süreci verdi. Matematik çemberindeki meslektaşların hepsi onun büyük bilgeliğinden etkilendi.
Kübitlerimiz ispat sürecini mümkün olan en popüler şekilde geri yükleyecek ve bu yüzyıllar arası bulmacayı çözmek için sizinle birlikte çalışacak Boole fonksiyonu duyarlılık varsayımı (Boole işlevi duyarlılık varsayımı).
İlk olarak Boole işlevleriyle başlayalım.
Boole işlevi
(Aşağıda Boole işlevlerinin açıklaması verilmiştir. Programlamaya aşina olanlar doğrudan ikinci kısma geçebilirler.)
Herhangi bir işlevi gerçekleştirmek için dijital devrelerin mantık kapılarının bir kombinasyonu ile uygulandığını biliyoruz. En yaygın iki mantık kapısı şunlardır: VE kapısı ile OR kapısı .
AND geçidi (AND), yalnızca girişin tümü 1 olduğunda 1 çıktı verir, aksi takdirde 0 çıkarır.
Veya bir giriş 1 olduğu sürece geçit (OR), çıkış 1'dir ve yalnızca girişin tümü 0 olduğunda çıkış 0'dır.
Ayrıca giriş (1,1) olduğunda, AND geçidi çok hassas , Girişlerden biri değiştiği sürece sonuç 0 olur. OR geçidi, her iki giriş de değiştiğinde yalnızca 0 olarak değişir.
AND geçidi ve OR geçidi, en basit durum olan yalnızca iki bit girişine sahiptir. N tane girdi biti girişi olduğunda, durum karmaşık hale gelir.
Günlük bir örnek vermek gerekirse, yıllarca para biriktirdiğinizde ve sonunda peşinatı ödediğinizde, ev kredisine başvurmak için bankaya gitmeniz gerekir.
Banka görevlisi size birçok sorudan oluşan bir form verdi. Sadece evet veya hayır yanıtlayabilir . Sonunda, doldurduğunuz içerik karmaşık bir süreçle işlendi, ancak kredinin size verilemeyeceği sonucuna varıldı.
Bu sürecin girdisi bir Boole değişkenidir (evet veya hayır) ve çıktı da bir Boole değişkenidir (kredinin onaylanıp onaylanmadığı), bu nedenle bir Boole işlevi .
Sonrasında tekrar düşündüğünüzde bazı soruların cevaplarını tersine çevirebileceğinizi düşünüyorsunuz ve belki yine de başvuruyu geçebilirsiniz. Sonunda, onayın sonucunu değiştirmek için 7'den fazla sorunun düzeltilmesi gerektiğini fark edersiniz.
Diyelim ki bu Boole işlevi, ilk cevabınızın koşulu altında Hassasiyet 7'dir .
Bir Boole işlevi f için, belirli bir girdi x olması durumunda (x, n bitlik bir Boole değişkenidir), s Boole değişkenlerinden daha fazlası değiştiğinde sonuç tersine çevrilir. Girdi x olduğunda Boole fonksiyonunun f duyarlılığının s (f, x) olduğunu varsayalım.
Tüm duyarlılıkların maksimum değeri s (f, x), Boolean işlevi f'nin duyarlılığı olarak adlandırılır.
1989'da Nisan ve Szegedy, s'nin n ile ilgili bir polinom olduğunu tahmin ettiler. Bu Boole fonksiyonu duyarlılık varsayımı (Boole işlevi duyarlılık varsayımı).
Boolean fonksiyon duyarlılığı varsayımının ortaya çıkışından bu yana, bilgisayar bilimi teorisindeki en sorunlu açık problemlerden biri olmuştur. Bunu çözmek, n-bit ikili sinyallerin iyi bilinen eşlik kontrolü gibi mantık devreleri ve algoritmalarındaki birçok teorik problemi çözecektir.
Geometrik bir oyun ol
Ancak Boolean fonksiyon duyarlılığı varsayımını doğrudan kanıtlamak çok zordur. Neyse ki 1992'de iki matematikçi Gotsman ve Linial bunu ustalıkla popüler bir geometri oyununa dönüştürdüler.
Sayısal devredeki n biti n boyutlu uzayda küpün köşelerine dönüştürdüler.
Örneğin, 2 bitlik bir girişin 4 olasılığı vardır: 00, 01, 10, 11. Karenin dört köşesine eşdeğer: (0,0), (0,1), (1,0), (1,1). Kare, iki boyutlu uzaydaki bir küptür.
Benzer şekilde, eğer 3 bit ise, üç boyutlu bir küpün 8 köşesine ve daha yüksek boyutlara karşılık gelir.
Küpte iki bitişik köşe Yalnızca bir koordinat değeri farklıdır Sırasıyla 0 ve 1'dir ve diğer koordinat değerleri tamamen aynıdır.
Bu nedenle, küpteki bir tepe noktasından bitişik köşesine geçmek, Boole işlevinin girdisindeki bir biti çevirmeye eşdeğerdir. (Olağanüstü!)
Bir Boole işlevinin girdisi köşe koordinatlarıyla temsil edilebildiğinden, çıktı ne olacak? Tanımlamak için iki renk kullanabiliriz.
Örneğin, kullanın Kırmızı 0, mavi 1 anlamına gelir . Bir köşe kırmızıysa, bu, köşenin üç koordinat değerinden oluşan 3 bitlik Boole işlevinin, Boolean işlevine girdikten sonra 0 alacağı anlamına gelir.
Örneğin:
Yukarıdaki şekilde Boolean fonksiyonunda giriş (0,1,1) ise çıkış 1 olacaktır.
İlk biti çevirirsek, neyse ki, Boole fonksiyonu bu değişikliğe duyarlı değildir ve çıktı hala 1'dir, bu şekilde tepe noktasını sağa hareket ettirmeye eşdeğerdir ve renk hala mavidir.
Bununla birlikte, üçüncü bit çevrildikten sonra, Boolean işlevi bu değişikliğe duyarlıdır ve çıktı 0 olur, bu da tepe noktasının altındaki noktayı hareket ettirmeye eşdeğerdir ve renk maviden kırmızıya değişir.
Belirli koşullar altında, girdi sonucunun herhangi bir biti ters çevrilirse, çıktı sonucu 1'den 0'a değişecektir, bu da mavi noktanın kırmızı noktalarla çevrili olduğu ve bu noktanın hassasiyetinin 0 olduğu ve mavi nokta olmadığı anlamına gelir. Doğrudan onunla bağlantı kurun.
Bir noktanın etrafındaki aynı renge sahip noktaların sayısı, bu tepe noktasındaki Boole işlevinin hassasiyetine eşittir. Boole işlevinin duyarlılığı, tüm köşelerin duyarlılığının maksimum değeridir.
Böylelikle Boole fonksiyonu duyarlılık varsayımı, N boyutlu bir küp üzerinde basit bir probleme indirgenebilir:
N boyutlu bir küpün köşelerinin yarısından fazlası kırmızıya ve geri kalanı maviye boyanmışsa, her zaman aynı renkten komşuları olan bazı kırmızı noktalar olur mu? Öyleyse, etrafındaki maksimum kırmızı nokta sayısı nedir?
Gotsman ve Linial'in orijinal sözleri şu şekildedir:
S, n boyutlu Boole hiperküpünün {0,1} n rastgele bir alt kümesi ve boyutu 2n-1 + 1 olsun. O halde S'de bir nokta olmalı ve S'de en azından nc komşular olmalı. (2n-1 + 1, n boyutlu küpün toplam köşelerinin tam olarak yarısından fazlasıdır.)
C'nin 0 ile 1 arasında bir sabit olduğu durumda, c = 1/2 olduğunu daha sonra görebiliriz.
Kırmızıya boyanmış köşeler, toplam köşe sayısının tam olarak yarısı kadarsa. Birbirlerine bitişik olmayabilirler. Üç boyutlu bir küpte bir örnek bulunabilir: dört nokta (0,0,0), (1,1,0), (1,0,1) ve (0,1,1) diyagonal boyunca çaprazdır. hat. (Aşağıdaki resimde kırmızı nokta)
Ancak, bir nokta daha kırmızıya boyandığı sürece, kırmızı noktalar arasında bir bağlantı olması gerekir.
İlham
Bile Boole fonksiyonu duyarlılık varsayımı 27 yıl önce basitleştirildi, ancak bu konu 20 yıldan fazla bir süredir rafa kaldırılmaya devam ediyor.
7 yıl öncesine kadar, Ph.D.'den yeni mezun olan Huang Hao, New Jersey Eyalet Üniversitesi'nde matematik profesörü olan Michael Saks ile yemek yedi ve bu varsayım hakkında diğer konuşmaları duydu.
Huang Hao, sessizce bu soruyu "görev listesine" ekledi.
Huang Hao, bu sorunu çözmek için 200 yıl önce bir matematik teoremi kullanmayı düşündü: Cauchy'nin Değişim Teoremi (Cauchy geçmeli teoremi).
Bu teorem, bir matrisin özdeğerlerini alt matrisleriyle ilişkilendirerek, onu yüksek ve düşük boyutlu küpler arasındaki ilişkiyi incelemek için mükemmel bir araç haline getirir. İki boyutlu bir küp (kare), üç boyutlu bir küpün yüzüdür ve bu nedenle ikincisinin bir alt kümesidir.
Cauchy'nin Değişim Teoremi İfade aşağıdaki gibidir:
A, n × n mertebesinde bir matris, B, A'nın m × m mertebesidir Ana alt matris (m < n). A matrisinin öz değeri 1 2 n, B matrisinin öz değeri 1 2 m, o zaman:
Zaten cevaba yakın, başka ne var? Para olabilir.
Huang Hao, bu konuyu daha fazla incelemek ve keşfetmek için Ulusal Bilim Vakfı'ndan bir hibe başvurusunda bulunmaya karar verdi.
Geçen ay, Huang Hao, Madrid'de bir otelde otururken ve bilimsel araştırma fonları için başvurusunu yazarken, aniden ilham aldı: Matristeki belirli sayıların sembollerini değiştirebilir ve sonucu elde edene kadar sertifika sürecini ilerletebilirsiniz.
Şu şekilde tanımlanan 2n × 2n dereceli matrisler kümesi oluşturdu:
Matematiksel tümevarım ile kolayca kanıtlanabilir:
Matris özdeğerlerinin tanımına göre, An'ın özdeğerleri sadece n ve -n olabilir.
Ve An'ın köşegen elemanlarının hepsi 0'dır, dolayısıyla matrisin izi Tr (An) = 0'dır. biliyoruz Matrisin izi, tüm özdeğerlerin toplamına eşittir , Yani n ve -n sayıları eşit olmalıdır, ikisi de 2n-1'dir.
H, m köşeli bir grafikse (aralarında noktalar ve bağlantılardan oluşan bir grafik), A simetrik bir matristir ve A, H'nin grafiğidir. Bitişik matris .
Sözde bitişik matris, A'nın u-inci satırı ve v-inci sütunundaki elemanı ifade eder ve H'nin u-inci noktası ile v-inci noktasının bitişik olup olmadığını gösterir. Eğer bitişik değillerse, bu eleman 0'a eşittir; eğer bitişikse, bu eleman -1 veya 1; ek olarak, köşegen eleman 0'a eşit olmalıdır.
Yukarıda oluşturduğumuz An matrisinin n boyutlu Qn küpünün bitişik matrisi olduğunu doğrulamak kolaydır.
H grafiğinin n boyutlu bir küpün bir parçası olduğunu varsayarsak (kesin olarak, Qn küpünün indüklenmiş alt grafiği olarak adlandırılır), bu durumda H'nin bitişik matrisi An'ın bir ana alt matrisidir.
1'in A matrisinin maksimum öz değeri olduğunu, v'nin 1'e karşılık gelen özvektör olduğunu ve v1'in özvektör v'deki en büyük mutlak değere sahip bileşen olduğunu varsayalım.
Yukarıdaki türetme sürecindeki ilk eşitsizlik işaretinin nedeni Toplamın mutlak değeri Daha az Mutlak değerlerin toplamı .
İkinci eşitsizlik işareti de çok basittir: (H), H grafiğinin duyarlılığı ve sol taraf, belirli bir noktanın duyarlılığı ve grafiğin duyarlılığı, tüm noktaların duyarlılığının maksimum değeridir.
Yani (H) | 1 |, yani H grafiğinin hassasiyeti (H), A matrisinin maksimum özdeğerinin mutlak değerinden daha büyüktür.
A, An'ın alt matrisidir. H 2n-1 + 1 köşeleri içeriyorsa, Cauchy'nin alternatif teoremine getirilir:
(H) | 1 |, yani (H) n ve (H) 'nin n-bit Boole fonksiyonunun duyarlılığı olduğu kanıtlanmıştır.
Kanıt bitti!
Huang Hao bu basit yolla şunu kanıtladı: n boyutlu küpteki noktaların yarısından fazlasının herhangi bir alt kümesinde, her zaman aynı rengin en az leastn diğer noktasına bağlı bazı noktalar olacaktır. Bu sonuçtan, hassas Derece varsayımı.
kuyruk
"Umarım Huang Hao, bu sonbaharda yüksek lisans derecesinin kombinatoryal matematik dersinde (ispat sürecini) öğretebilir. Sadece bir sınıf yeterlidir."
Fransız Ulusal Araştırma Merkezi'nden Clarie Mathieu, Huang Hao'nun kanıtını gördüğünde, yardım edemedi ama ispat sürecinin basitliğinden yakınıyordu.
Huang Hao'nun sonuçları, hassasiyet varsayımını kanıtlamak için gerekli olanları bile aşıyor ve ayrıca karmaşıklık ölçütleri hakkında yeni içgörüler oluşturmalıdır. Örneğin, n-bit ikili dizeler için bir eşlik kontrol algoritması.
Columbia Üniversitesi'nde bilgisayar bilimi profesörü olan Servedio, "Bu, Boolean fonksiyon analizindeki diğer soruları yanıtlamaya yardımcı olmak için araç setimize katkıda bulunuyor," dedi ve "Bence o gece birçok insan bu haberi duyduktan sonra daha rahat uyuyacak."
Huang Hao'yu birdenbire ilham veren şeyin ne olduğunu bilmiyorum, ancak bir netizen bir olasılıktan bahsetti: bilimsel bir araştırma fonu başvurusu yazmak bilimsel araştırmaya gerçekten yardımcı olabilir (gülüyor).
Huang Hao hakkında
Huang Hao, 2007 yılında Pekin Üniversitesi Matematik Bölümü'nden mezun oldu ve ileri eğitim için California Üniversitesi, Los Angeles'a gitti. 2012 yılında Matematik alanında doktora derecesini aldı ve o yıl tez bursunu aldı.
Mezun olduktan sonra Princeton Üniversitesi İleri Araştırmalar Enstitüsü'nde ve Minnesota Üniversitesi Matematik Enstitüsü'nde doktora sonrası araştırmacı olarak çalıştıktan sonra Emory Üniversitesi Matematik Bölümüne yardımcı doçent olarak girdi ve Journal of Combinatorial Theory'de ve diğer akademik dergilerde art arda 21 akademik makale yayınladı.
Huang Hao'nun ana araştırma yönleri, aşırı değer ve olasılık kombinasyonu, yapısal grafik teorisi ve teorik bilgisayar bilimidir.
Portal
Kağıt bağlantısı:
Hiperküplerin indüklenmiş alt grafikleri ve Hassasiyet Varsayımının bir kanıtı
https://arxiv.org/abs/1907.00847
- Bitiş -
Samimi işe alım
Qubit, editörleri / muhabirleri işe alıyor ve merkezi Pekin, Zhongguancun'da bulunuyor. Yetenekli ve hevesli öğrencilerin bize katılmasını dört gözle bekliyoruz! Ayrıntılar için, lütfen QbitAI diyalog arayüzünde "işe alım" kelimesiyle yanıt verin.
Qubit QbitAI · Toutiao İmzalama Yazarı
' ' Yapay zeka teknolojisi ve ürünlerindeki yeni eğilimleri takip edin
