Karmaşıklık Teorisinin Bilginin Sınırlarına 50 Yıllık Yolculuğu | Quanta Dergisi

2007 güz döneminin ilk haftasında Marco Carmosino, Amherst'teki Massachusetts Üniversitesi'ndeki tüm bilgisayar bilimleri ana dalları için gerekli olan bir matematik dersine kendini sürükledi. İkinci sınıf öğrencisi olan Carmosino, video oyunları tasarlamak için üniversiteyi bırakmayı düşünüyordu. Sonra profesör hayatının akışını değiştirecek basit bir soru sordu: Matematiğin gerçekten işe yaradığını nereden biliyorsun?

"Bu, benim oturup dikkatimi toplamamı sağladı," diye anımsıyordu Carmosino, şimdi IBM'de teorik bir bilgisayar bilimcisi. Baş döndürücü kendine gönderme yapan argümanları ilk kez matematiksel muhakemenin sınırlarını ortaya çıkaran ve hesaplamanın temel sınırları üzerine gelecekteki tüm çalışmaların temelini oluşturan Kurt Gödel'in çalışmaları üzerine isteğe bağlı bir seminere kaydoldu. Alınacak çok şey vardı.

Carmosino, "%100 anlamadım," dedi. "Ama bunu istediğimi biliyordum."

Bugün, tecrübeli araştırmacılar bile, teorik bilgisayar bilimindeki P'ye karşı NP problemi olarak bilinen merkezi açık soruyla karşılaştıklarında, yetersiz bir anlayış buluyorlar. Özünde, bu soru, uzun süredir son derece zor olduğu düşünülen birçok hesaplama probleminin gerçekten kolayca çözülüp çözülemeyeceğini (henüz keşfetmediğimiz gizli bir kısayol aracılığıyla) veya çoğu araştırmacının şüphelendiği gibi gerçekten zor olup olmadığını sorar. Tehlikede olan, bilinebilir olanın doğasından başka bir şey değildir.

Hesaplama karmaşıklığı teorisi alanındaki araştırmacıların onlarca yıllık çabalarına rağmen - farklı problemlerin özündeki zorluklarla ilgili bu tür soruların incelenmesi - P'ye karşı NP sorusuna bir çözüm bulmak zor. Ve olası bir kanıtın nereden başlaması gerektiği bile net değil.

“Yol haritası yok” dedi Michael SipserMassachusetts Institute of Technology'de 1980'lerde bu sorunla boğuşarak yıllarını harcayan deneyimli bir karmaşıklık teorisyeni. "Sanki vahşi doğaya gidiyormuşsun gibi."

Hesaplamalı problemlerin çözülmesinin zor olduğunu kanıtlamanın başlı başına zor bir iş olduğu görülüyor. Ama neden bu kadar zor? Ve ne kadar zor? Carmosino ve meta-karmaşıklık alt alanındaki diğer araştırmacılar, bunun gibi soruları hesaplamalı problemler olarak yeniden formüle ederek, karmaşıklık teorisinin merceğini kendi üzerine çevirerek alanı ileriye taşıyor.

“'Tamam, bu çok havalı' diye düşünebilirsiniz. Belki de karmaşıklık teorisyenleri çıldırmıştır'” dedi. Rahul IlangoMIT'de son zamanlarda bu alandaki en heyecan verici sonuçlardan bazılarını üreten bir yüksek lisans öğrencisi.

Araştırmacılar, bu içe dönük soruları inceleyerek, hesaplama zorluğunu kanıtlamanın zorluğunun, ilk başta ilgisiz görünebilecek temel sorulara yakından bağlı olduğunu öğrendiler. Görünüşe göre rastgele verilerde gizli kalıpları tespit etmek ne kadar zor? Ve eğer gerçekten zor problemler varsa, bunlar ne sıklıkla zordur?

"Meta-karmaşıklığın her şeyin kalbine yakın olduğu ortaya çıktı" dedi Scott Aaronson, Austin Texas Üniversitesi'nde bir karmaşıklık teorisyeni.

Bu, araştırmacıları P'ye karşı NP probleminden meta-karmaşıklığa götüren uzun ve dolambaçlı yolun hikayesidir. Kolay bir yolculuk olmadı - yol yanlış dönüşler ve barikatlarla dolu ve tekrar tekrar kendi döngüsüne giriyor. Yine de meta-karmaşıklık araştırmacıları için, keşfedilmemiş bir manzaraya yapılan bu yolculuk başlı başına bir ödül. Görünüşte basit sorular sormaya başla, dedi Sevgililer Günü KabanetleriKanada'daki Simon Fraser Üniversitesi'nde bir karmaşıklık teorisyeni ve "nereye gideceğiniz hakkında hiçbir fikriniz yok."

Bilinen Bilinmeyenler

P'ye karşı NP problemi, cansız adını, karmaşıklık teorisyenlerinin hesaplama problemlerini geniş "" şeklinde sınıflandırma alışkanlığına borçludur.karmaşıklık sınıfları” Nasdaq hisse senedi sembollerini düşündüren etiketlerle. Hesaplamalı bir problem, prensip olarak bir algoritma ile çözülebilen bir problemdir - kesin olarak belirlenmiş bir talimat listesi. Ancak tüm algoritmalar eşit derecede yararlı değildir ve algoritmalar arasındaki farklılıklar, farklı sınıflardaki problemler arasındaki temel farklılıklara işaret eder. Karmaşıklık teorisyenleri için zorluk, bu ipuçlarını karmaşıklık sınıfları arasındaki ilişkiler hakkında kesin teoremlere dönüştürmektir.

Bu ilişkiler, herhangi bir özel teknolojinin çok ötesine geçen hesaplamayla ilgili değişmez gerçekleri yansıtır. Kabanets, "Bu, evrenin yasalarını keşfetmek gibidir" dedi.

“P” ve “NP” bir grubun en ünlü iki üyesidir. büyüyen hayvanat bahçesi yüzlerce karmaşıklık sınıfından Kabaca söylemek gerekirse, P, bir listenin alfabetik sıralanması gibi kolayca çözülebilen problemler sınıfıdır. NP, sudoku bulmacaları gibi kolayca kontrol edilebilen çözümlere sahip problemler sınıfıdır. Kolayca çözülebilen tüm problemlerin kontrol edilmesi de kolay olduğundan, P'deki problemler de NP'dedir. Ancak bazı NP problemlerini çözmek zor görünüyor - önce birçok olasılığı denemeden bir sudoku bulmacasının çözümünü hemen sezemezsiniz. Bu bariz sertlik sadece bir yanılsama olabilir mi - kolayca kontrol edilebilen her sorunu çözmek için tek bir basit numara var mı?

Eğer öyleyse, o zaman P = NP: İki sınıf eşdeğerdir. Eğer durum buysa, muazzam sudoku bulmacalarını çözmeyi, küresel nakliye rotalarını optimize etmeyi, son teknoloji şifrelemeyi kırmayı ve matematik teoremlerinin kanıtlarını otomatikleştirmeyi önemsiz kılan bir algoritma olmalı. Eğer P ≠ NP ise, prensipte çözülebilen birçok hesaplama problemi pratikte sonsuza kadar kavrayışımızın ötesinde kalacaktır.

Araştırmacılar, P'ye karşı NP problemi ilk kez dile getirilmeden çok önce, hatta modern bilgisayar biliminin başlangıcından çok önce, biçimsel matematiksel akıl yürütmenin sınırları hakkında endişeleniyorlardı. 1921'de, yaklaşık bir asır sonra Carmosino'nun dikkatini çekecek olan aynı soruyla mücadele eden matematikçi David Hilbert, matematiği mutlak kesinliğe dayandırmak için bir araştırma programı önerdi. Aksiyom adı verilen birkaç basit varsayımdan başlamayı ve üç temel kriteri karşılayan birleşik bir matematik teorisi türetmeyi umuyordu.

Hilbert'in ilk koşulu olan tutarlılık, matematiğin çelişkilerden arınmış olması için temel gereksinimdi: Aynı aksiyomlardan yola çıkarak birbiriyle çelişen iki önerme kanıtlanabilseydi, tüm kuram kurtarılamaz olurdu. Ancak bir teori çelişkisiz olabilir ve kapsamı yine de sınırlı olabilir. Hilbert'in ikinci koşulu olan eksiksizlik için motivasyon buydu: tüm matematiksel ifadelerin ya kanıtlanabilir şekilde doğru ya da kanıtlanabilir şekilde yanlış olması gerekliliği. Üçüncü kriteri olan karar verilebilirlik, herhangi bir matematiksel ifadenin doğru mu yoksa yanlış mı olduğunu belirlemek için kesin bir mekanik prosedür gerektiriyordu. 1930'da bir konferansta konuşan Hilbert, "Sloganımız 'Bilmeliyiz, bileceğiz' olacak" dedi.

Sadece bir yıl sonra Gödel, Hilbert'in rüyasına ilk darbeyi vurdu. O kanıtladı "bu ifade kanıtlanamaz" gibi kendi kendini baltalayan bir ifadenin herhangi bir uygun aksiyom dizisinden türetilebileceğini. Böyle bir ifade gerçekten kanıtlanamazsa, teori eksiktir, ancak kanıtlanabilirse, teori tutarsızdır - daha da kötü bir sonuç. Aynı makalede Gödel, hiçbir matematiksel teorinin kendi tutarlılığını asla kanıtlayamayacağını da kanıtladı.

Araştırmacılar, zorunlu olarak eksik olsa da, gelecekteki bir matematik teorisinin yine de karar verilebilir olduğunun kanıtlanabileceğine dair umutlarını sürdürdüler. Belki de Gödel'inki gibi can sıkıcı önermelerden uzak dururken tüm kanıtlanabilir ifadeleri tanımlayacak prosedürler geliştirebilirler. Sorun, hiç kimsenin bu varsayımsal prosedürler hakkında nasıl akıl yürüteceğini bilmemesiydi.

Sonra 1936'da Alan Turing adlı 23 yaşındaki bir yüksek lisans öğrencisi, Hilbert'in karar verilebilirlik koşulunu o zamanlar alışılmadık olan hesaplama dilinde yeniden ifade etti ve ona ölümcül bir darbe indirdi. Turing, şimdi bilinen adıyla matematiksel bir model formüle etti. Turing makinesi - bu, tüm olası algoritmaları temsil edebilir ve Hilbert'in prosedürü mevcut olsaydı, bu modele uyacağını gösterdi. Daha sonra Gödel'inki gibi kendine referanslı yöntemler kullandı. kanıtlamak karar verilemez ifadelerin varlığı - veya eşdeğer olarak, hiçbir algoritmanın çözemeyeceği hesaplanamayan problemler.

Hilbert'in programı harabeye dönmüştü: Neyin kanıtlanabileceği ve neyin hesaplanabileceği konusunda sonsuza dek temel sınırlar olacaktı. Ancak bilgisayarlar teorik soyutlamalardan gerçek makinelere dönüştükçe araştırmacılar, Turing'in çözülebilir ve çözülemez problemler arasındaki basit ayrımının birçok soruyu cevapsız bıraktığını fark ettiler.

1960'lara gelindiğinde, bilgisayar bilimciler bazı sorunları çözmek için hızlı algoritmalar geliştirirken, diğerleri için bilinen tek algoritmalar dayanılmaz derecede yavaştı. Ya soru sadece sorunların çözülebilir olup olmadığı değil, çözmenin ne kadar zor olduğuysa?

Carmosino, "Zengin bir teori ortaya çıkıyor ve artık yanıtları bilmiyoruz," dedi.

Iraksak Yollar

Sertlikle ilgili soruların ne kadar kafa karıştırıcı olabileceğini göstermek için, grafikleri içeren yakından ilişkili bir çift problemi ele alalım. Bunlar, düğüm adı verilen, çizgilerle birbirine bağlanan, kenar adı verilen nokta ağlarıdır. Bilgisayar bilimcileri onları her şeyi modellemek için kullanıyor. kuantum hesaplama için trafik akışı.

Size bir grafik verildiğini ve Hamilton yolu denen bir şey bulmanız istendiğini varsayalım - her düğümden tam olarak bir kez geçen bir yol. Bu sorun prensipte açıkça çözülebilir: Yalnızca sınırlı sayıda olası yol vardır, bu nedenle her şey başarısız olursa her birini kontrol edebilirsiniz. Yalnızca birkaç düğüm varsa sorun değil, ancak biraz daha büyük grafikler için bile olasılıkların sayısı kontrolden çıkarak bu basit algoritmayı hızla işe yaramaz hale getiriyor.

Daha iyi bir mücadele ortaya koyan daha sofistike Hamilton yolu algoritmaları vardır, ancak algoritmaların sorunu çözmek için ihtiyaç duyduğu süre, grafiğin boyutuyla birlikte her zaman katlanarak artar. Araştırmacıların keşfettiği en iyi algoritma bile "makul bir süre içinde" bir yol bulamadan önce grafiklerin çok büyük olması gerekmez. Russel İmpagliazzo, San Diego, California Üniversitesi'nde bir karmaşıklık teorisyeni. "Ve 'makul süre' derken, 'evren sona ermeden önce' demek istiyorum.”

Hamiltoniyen yol probleminin bir başka ilginç özelliği daha vardır. Birisi belirli bir grafik üzerinde bir Hamilton yolu bulduğunu iddia ederse, grafik çok büyük olsa bile çözümün geçerli olup olmadığını hızlıca kontrol edebilirsiniz. Tek yapmanız gereken yolu takip etmek ve düğümleri birer birer işaretlemek, herhangi bir düğümü iki kez işaretlemediğinizden emin olmak için kontrol etmek. Sonunda hiçbir düğüm eksik değilse, yol Hamiltoniyendir.

Bu çözüm kontrol algoritmasını çalıştırmak için gereken süre, grafiğin boyutuyla orantılıdır. Bu, onu, grafik boyutunun polinom fonksiyonları olarak çalışma süreleri artan daha geniş polinom algoritmaları kategorisine sokar. Polinom büyümesi, üstel büyümeye kıyasla daha uysaldır, bu nedenle polinom algoritmaları büyük grafiklerde bile geçerliliğini korur. Carmosino, "Önemli ölçüde daha verimli," dedi.

Hamilton yolu probleminin kesin bir asimetrisi vardır: Hızlı bir polinom algoritması kullanarak doğru bir çözümü doğrulayabilirsiniz, ancak bir çözüm bulmak için yavaş bir üstel algoritmaya ihtiyacınız olacaktır. Bu asimetri şaşırtıcı gelmeyebilir - sanatsal bir şaheseri tanımak, yaratmaktan daha kolaydır, matematiksel bir kanıtı kontrol etmek, yeni bir teoremi kanıtlamaktan daha kolaydır - yine de tüm hesaplama problemlerinde bu asimetrik karakter yoktur. Aslında, Hamilton yollarını bulmaya çok benzeyen bir problem oldukça farklı davranır.

Diyelim ki size yine bir grafik verildi, ama şimdi sizden her kenarı tam olarak bir kez geçen bir “Euler yolu” bulmanız isteniyor. Yine, olası çözümleri kontrol etmek için bir polinom algoritması var, ancak bu sefer sorunu çözmek için bir polinom algoritması da var. Burada asimetri yok. Karmaşıklık teorisinde, bazı yolları bulmak diğerlerinden daha kolay görünüyor.

Hem Hamilton yolu sorunu hem de Euler yolu sorunu, çözümleri polinom algoritmaları tarafından kontrol edilebilen tüm sorunları içerecek şekilde tanımlanan NP karmaşıklık sınıfındadır. Euler yolu problemi de P sınıfına girer çünkü bir polinom algoritması onu çözebilir, ancak görünüşe göre bu Hamilton yolu problemi için doğru değil. Yüzeysel olarak bu kadar benzer olan bu iki grafik problemi neden bu kadar çarpıcı biçimde farklı olsun? P'ye karşı NP probleminin özü budur.

Evrensel Sert

İlk başta, karmaşıklık sınıfları benzer olan ancak doğrudan ilişkili olmayan problemleri sıralamak için uygun kategoriler gibi görünüyordu - hiç kimse Hamilton yollarını bulmanın diğer zor hesaplama problemleriyle bir ilgisi olduğundan şüphelenmedi.

Daha sonra 1971'de, Amerika Birleşik Devletleri'nde görev süresi reddedildikten sonra Toronto Üniversitesi'ne taşındıktan sonraki bir yıl içinde, karmaşıklık teorisyeni Stephen Cook yayınlanan bir olağanüstü sonuç. Garip bir özelliğe sahip belirli bir NP problemini tanımladı: Eğer bu problemi çözebilecek bir polinom algoritması varsa, NP'deki diğer tüm problemleri de çözebilir. Görünüşe göre Cook'un "evrensel" problemi, görünüşte zor problemler sınıfını destekleyen ve onları aşağıdaki kolay problemlerden ayıran tek bir sütundu. Bu sorunu çöz ve NP'nin geri kalanı çökecek.

Cook, evrensel sorunu için hızlı bir algoritma olmadığından şüphelendi ve makalenin ortalarında bunu söyleyerek, "Bu varsayımı kanıtlamak için büyük çaba harcamaya değer olduğunu düşünüyorum" dedi. "Önemli çaba" yetersiz bir ifade olacaktır.

Aynı sıralarda, Sovyetler Birliği'nde bir yüksek lisans öğrencisi adında Leonid Levin kanıtladı benzer sonuç, birkaç farklı evrensel sorunu tanımlaması dışında. Ayrıca, Amerikan karmaşıklık teorisyeni Richard Karp kanıtladı Cook'un (ve Levin'in, Karp ve Cook'un Levin'in çalışmalarını yıllar sonrasına kadar bilmemesine rağmen) tanımladığı evrensellik özelliğinin kendisinin neredeyse evrensel olduğunu. Bilinen bir polinom algoritması olmayan neredeyse her NP problemi - yani zor görünen hemen hemen her kolayca kontrol edilebilen problem - NP-tamlığı olarak bilinen aynı özelliğe sahipti.

Bu, tüm NP-tam problemler anlamına gelir - Hamilton yolu problemi, sudoku ve Binlerce diğerleri - kesin anlamda eşdeğerdir. Ilango, "Bütün bu farklı doğal görevleriniz var ve hepsinin sihirli bir şekilde aynı görev olduğu ortaya çıkıyor" dedi. "Aynı görevin mümkün olup olmadığını hala bilmiyoruz."

Herhangi bir NP-tamamlama probleminin zorluğunu çözmek, P'ye karşı NP sorusunu çözmek için yeterli olacaktır. P ≠ NP ise, kolay ve zor problemler arasındaki ayrım, hepsi eşit derecede güçlü olan binlerce sütun tarafından desteklenir. P = NP ise, tüm yapı tek bir parçanın düşmesini bekleyerek yıkılmanın eşiğindedir.

Cook, Levin ve Karp pek çok ilgisiz gibi görünen sorunları birleştirmişti. Şimdi karmaşıklık teorisyenlerinin yapması gereken tek şey bir sorunu çözmekti: P = NP mi yoksa değil mi?

Elli yıl sonra, soru cevapsız kalır. Kabanets, hesaplamanın sınırları hakkında akıl yürütmeyi, büyük resmi anlamadan geniş bir alanı araştırmaya benzetiyordu. Sınırsız hesaplama gücüne sahip bir varlık, bir dağın tepesinden aşağıya bakıp tüm manzarayı bir kerede görebilir, ancak sıradan ölümlüler bu tür bir avantaja güvenemez. "Dağın dibindeki bizler, daha iyi bir görüş için yukarı ve aşağı zıplamayı deneyebiliriz" dedi.

P = NP olduğunu varsayalım. Bunu kanıtlamak için, araştırmacıların, o uçsuz bucaksız manzaranın karanlık bir köşesinde saklanıyor olabilecek bir NP-tam problemi için hızlı bir algoritma bulmaları gerekecek. Yakın zamanda bulacaklarının garantisi yok: Karmaşıklık teorisyenleri ara sıra keşfetti sadece onlarca yıllık çalışmanın ardından zor görünen (NP-tamamlanmamış olsa da) problemler için ustaca algoritmalar.

Şimdi P ≠ NP olduğunu varsayalım. Bunu kanıtlamak daha da zor görünüyor. Karmaşıklık teorisyenleri, gelecekteki tüm araştırmacıların en iyi çabalarını etkili bir şekilde tahmin ederek ve engelleyerek, hiçbir hızlı algoritmanın var olamayacağını belirlemelidir.

Nereden başlayacağını bilememek sorunun bir parçasıdır. Ancak araştırmacıların denemediği gibi değil. Onlarca yıldır soruna birçok açıdan saldırdılar ve her fırsatta yolun tıkandığını gördüler. Carmosino, "Teorik bilgisayar bilimindeki en bariz gerçeklerden biri bu," dedi. "Bu kadar kalıcı bir fenomeniniz olduğunda, biraz açıklama istersiniz."

Carmosino'nun üniversitedeki son yılında, merakı onu Gödel'den karmaşıklık teorisi üzerine bir yüksek lisans kursuna yöneltmişti. Peri masallarının anlatı yapısını öğrenip yenilerini üreten bir bilgisayar programı olan tutku projesine değil, ev ödevlerine daha fazla zaman harcadığını fark edince şaşırdı.

Carmosino, "'Vay canına, bunu ciddiye almam gerekiyor' diye düşündüm," diye hatırladı. Çok geçmeden kendini konuya o kadar kaptırdı ki akıl hocası nazikçe mezuniyet sonrası planlarını yeniden gözden geçirmesini önerdi.

Carmosino, "'Biliyorsunuz, bunu yapmaya devam etmek istiyorsanız, teorik bilgisayar bilimi ve karmaşıklık teorisi yapmaya devam etmek istiyorsanız, şunları yapabilirsiniz: Buna yüksek lisans denir' gibiydi" dedi. Yüksek lisansını aldıktan sonra, Impagliazzo'nun gözetiminde doktora yapmak için 2012'de San Diego'ya taşındı.

Carmosino'nun asıl amacı, başlangıçta, bir konuyu daha iyi anlamaktı. dönüm noktası kağıdı yirmi yıl öncesinden, bu onun hayal gücünü ele geçirmişti. Bu makale, karmaşıklık teorisyenleri tarafından Alexander Razborov ve Steven Rudich, P ≠ NP'yi kanıtlamak için belirli bir "doğal" stratejinin neredeyse kesin olarak başarısız olacağını, çünkü başarının araştırmacıların pek olası görmediği yüksek bir maliyetle - kriptografinin tamamen çökmesiyle - geleceğini göstermişti. Araştırmacılar, Razborov ve Rudich'in sonucunu P ≠ NP'yi kanıtlamaya yönelik bu popüler yaklaşımın önünde bir engel olarak yorumladılar.

Bu "doğal kanıtlar engeli", karmaşıklık teorisindeki açık problemleri çözmenin önündeki bilinen birçok engelden sadece biridir. Her biri, görünüşte umut verici bir yolun aslında bir çıkmaz sokak olduğu konusunda uyarıda bulunan bir barikat görevi görür. Birlikte, bu engeller, P'ye karşı NP problemini çözen herhangi bir kanıtın, geçmişte kullanılan herhangi bir kanıttan kökten farklı olması gerektiğini gösterir; bu nedenle çoğu araştırmacı bir çözümün çok uzakta olduğuna inanıyor. Ama en azından engeller onlara nereye bakmamaları gerektiğini söylüyor.

Ilango, "Karmaşıklık teorisi, pek çok engelle hem lanetlenmiş hem de kutsanmıştır" dedi.

Carmosino doğal kanıtlarla karşılaştığında neredeyse 20 yaşındaydı. Ancak araştırmacılar için daha fazla ders içerdiğinden şüpheleniyordu. O ve üç meslektaşı, meta-karmaşıklık perspektifinden doğal kanıtlar engelini inceleyerek şaşırtıcı bir sonuç kanıtladıklarında, bu duygu bir gün haklı çıkacaktı. Kanıtları, meta-karmaşıklığa yeni bir ilgi uyandıran ve son birkaç yılda bir ilerleme telaşına yol açan birkaç önemli sonuçtan biriydi.

Ancak doğal kanıt engelinden meta-karmaşıklığa giden yolu takip etmek için, araştırmacıları 1970'lerde P'ye karşı NP problemini ilk kez çözmeye başladıklarında bıraktığımız yere geri atlamalıyız. Sorunları zor bir şekilde kanıtlamayı bu kadar zorlaştıran şey neydi?

Dolambaçlı Bir Yol

İlk başta araştırmacılar, Turing'in bazı problemlerin herhangi bir algoritma tarafından çözülemeyeceğini kanıtlamak için kullandığı tekniklerin varyasyonlarını kullanarak P ≠ NP'yi kanıtlamaya çalıştı - yani bazı NP problemlerinin herhangi bir olası polinom algoritması ile çözülemeyeceğini kanıtlamaya çalıştı. . Ama onlar hızlı keşfetti bu yöntemlerin işe yaramayacağına dair bir kanıt - P'ye karşı NP sorusunu çözmenin önündeki ilk büyük engel. Böylece başka bir yaklaşım aramaya başladılar ve çok geçmeden Turing'in çağdaş çalışmalarında bir tane buldular. Claude Shannon.

Kuzey Michigan'da küçük bir kasabada büyümüş olan Shannon, bilgi çağını başlatacak gibi görünmüyordu. Yine de, elektrik mühendisliği ve matematiksel mantıkta kendini eşit derecede evinde hissederek, yeni ortaya çıkan bilgisayar bilimi disiplininin disiplinler arası doğasını örnekledi. onun içinde yüksek lisans teziShannon, elektromekanik anahtarlardan yapılan devrelerin, Boole değişkenlerini içeren mantıksal ifadeleri nasıl temsil edebildiğini gösterdi - yalnızca iki değer (doğru veya yanlış veya 1 ve 0 gibi) alabilen nicelikler.

Bu ifadelerde, Boolean değişkenleri AND, OR ve NOT "mantık kapıları" ile birbirine bağlanır. Örneğin A AND B temel ifadesi, hem A hem de B doğru olduğunda doğrudur, aksi takdirde yanlıştır; Öte yandan A VEYA B, iki değişkenden en az biri doğruysa doğrudur. NOT geçidi daha da basittir: Tek bir değişkenin değerini tersine çevirir. Bu temel yapı taşlarından yeterincesiyle, herhangi bir hesaplamayı gerçekleştirebilirsiniz.

“Günün sonunda bilgisayarınıza baktığınızda, ne yapıyor? Bir devre çalıştırıyor, ”dedi Ilango.

Shannon'ın çalışması, söz konusu devreler sadece matematiksel soyutlamalar olsa da, teorisyenlere "devre karmaşıklığı" adı verilen hesaplama problemlerinin zorluğu hakkında düşünmeleri için yeni bir yol önerdi. Bir süre, araştırmacılar bu yaklaşımın P'ye karşı NP'yi çözmenin yolu olabileceğini düşündüler, ancak sonunda iz, doğal kanıtlar engeline çarptı.

Devre karmaşıklığı çerçevesi, Turing'in hesaplama modelindeki en temel kavramların yeniden düşünülmesini gerektirir. Burada, hesaplama sorunları ve bunları çözen algoritmalar yerine, araştırmacılar Boolean fonksiyonlarını ve bunları hesaplayan devreleri göz önünde bulundururlar. Bir Boole işlevi, Boole değişkenlerini (doğrular ve yanlışlar, 1'ler ve 0'lar) alır ve doğru veya yanlış, 1 veya 0 olarak çıktı verir. Ve bir algoritma gibi, bir devre herhangi bir girdi verildiğinde bir çıktı üretme prosedürünü tanımlar.

"Anladığım kadarıyla insanlar Turing makinelerinin çok karmaşık olduğuna karar verdikleri için devre karmaşıklığı üzerinde çalışmaya başladılar" dedi. Ryan WilliamsMIT'de bir karmaşıklık teorisyeni. "Devreleri kapı kapı inceleyebiliriz."

Herhangi bir hesaplama problemini çözmek için, bazıları diğerlerinden daha hızlı olan birçok algoritma olabileceği gibi, birçok farklı devre de herhangi bir Boole işlevini hesaplayabilir, bazıları diğerlerinden daha az kapıya sahiptir. Araştırmacılar, bir fonksiyonun devre karmaşıklığını, onu hesaplayan en küçük devredeki toplam kapı sayısı olarak tanımlar. Sabit sayıda giriş değişkeni olan bir işlev için, devre karmaşıklığı da sabit bir sayıdır - bazı işlevler için diğerlerinden daha yüksektir.

Ancak birçok durumda, girdi değişkenlerinin sayısını artırarak aynı işlevin daha karmaşık sürümlerini düşünebilirsiniz, tıpkı daha büyük grafikleri dikkate alarak Hamilton yolu problemini zorlaştırabileceğiniz gibi. Araştırmacılar daha sonra algoritma çalışma sürelerini incelerken sordukları aynı soruyu göz önünde bulundururlar: Bir Boole işlevini hesaplamak için gereken minimum kapı sayısı, girdi değişkenlerinin sayısı arttıkça polinom olarak mı yoksa üstel olarak mı büyüyor? Araştırmacılar bu iki fonksiyon kategorisini sırasıyla "hesaplaması kolay" ve "hesabı zor" olarak adlandırıyor.

Hesaplaması kolay bir Boole işlevi, P sınıfındaki bir hesaplama problemine benzer - polinom zamanında çalışan bir algoritma tarafından çözülebilen bir problem. Ancak, araştırmacıların giderek daha büyük sürümleri hesaplamak için keşfettikleri en iyi yolun katlanarak artan sayıda kapı gerektirdiği, ancak yanıtın kolayca kontrol edilebildiği, zor NP problemlerine benzer işlevler de vardır. Karmaşıklık teorisyenleri böyle bir işlevi hesaplamanın gerçekten daha iyi bir yolu olmadığını kanıtlayabilirlerse, bu P ≠ NP anlamına gelir.

Bu, çoğu karmaşıklık kuramcısının 1980'lerde izlediği stratejiydi. Ve ihtimaller onların tarafındaydı. Shannon vardı kanıtladı 1949'da hemen hemen her Boole doğruluk tablosu (bu, sabit boyutlu bir Boole işlevinin tüm olası giriş ve çıkışlarının yalnızca uzun bir listesidir), pratikte olabildiğince yüksek devre karmaşıklığına sahiptir. Şaşırtıcı derecede basit bir argüman kullandı: Az sayıda kapıyı birleştirmenin, birçok kapıyı birleştirmenin yollarından çok daha az yolu vardır.

Aaronson, "Etrafta dolaşacak kadar küçük devre yok," dedi.

Dolayısıyla karmaşıklık teorisyenleri kendilerini ilginç bir durumda buldular. Neredeyse her doğruluk tablosunun yüksek devre karmaşıklığı varsa, o zaman hemen hemen her Boole fonksiyonunun hesaplanması zor olmalıdır. Araştırmacıların, NP sınıfında olduğu bilinen tek bir işlevi tanımlaması gerekiyordu. Ne kadar zor olabilir ki?

Kripto Kardeşler

İlk başta, ilerleme hızlıydı. 1981'de Sipser ve iki işbirlikçi kanıtladı kapıların nasıl düzenlenebileceği konusunda belirli kısıtlamalara sahip devreler kullanıyorlarsa, belirli bir Boole fonksiyonunu hesaplamanın kesinlikle zor olduğunu.

Sipser, "Fantezi, bu kısıtlı modeller hakkında bir şeyler kanıtlayabilmeniz ve daha sonra öğrendiklerinizi daha az kısıtlamayla çalışmak için inşa edebilmenizdi" dedi.

1985'te Razborov bir sonraki büyük adımı attı. Moskova'da yüksek lisans okuluna yeni başlamıştı ve matematiğin farklı bir dalındaki bir problemle uğraşırken tesadüfen bu çabaya katılmıştı, burada P'ye karşı NP problemini çözmenin bir önkoşul olduğu ortaya çıktı.

Razborov, "Bu sorunun ne kadar zor olduğunu bilmediğim için şanslıydım," dedi. "Yoksa belki başlamazdım bile."

Razborov, yalnızca AND ve OR kapılarını içeren devreleri analiz etti ve kanıtladı kapılar nasıl düzenlenirse düzenlensin, bu tür devreleri kullanarak belirli bir işlevi hesaplamanın zor olduğunu - dahası, bu işlevin NP-tam olduğu biliniyordu. Araştırmacıların P'ye karşı NP'yi çözmek için yapması gereken tek şey, Razborov'un tekniklerini NOT kapıları olan devrelere genişletmekti.

Razborov, "Bir adım daha, bir vuruş daha yaparsak başaracağımıza dair evrensel bir his vardı" dedi. Ama öyle olmadı. Razborov'un kendisi, karışıma NOT kapıları eklenirse yönteminin başarısız olacağını ve kimsenin başka bir yol bulamayacağını kanıtladı. Yıllar geçtikçe, yolun neden tükendiğini merak etmeye başladı.

Amerika Birleşik Devletleri'nde Rudich aynı soruyu düşünüyordu. O ve Impagliazzo, birlikte yüksek lisansa giden üniversite sınıf arkadaşlarıydı. Dostlukları, Gödel ve Turing'in kendine gönderme yapan kanıtlarına ve bunların matematik ve bilgisayar biliminin temelleri üzerindeki çıkarımlarına duydukları ortak hayranlıkla alevlenmişti.

Impagliazzo, "Şakamız, 'öz referans' yazan bir düğme alacak olmamızdı" dedi.

Yüksek lisans öğrencileri olarak, hem Rudich hem de Impagliazzo, P ≠ NP'yi kanıtlamaya çalışmak için belki de en iyi pratik motivasyonu sunan bir konu olan kriptografinin karmaşıklık-teorik temelleri üzerinde çalıştılar. Kriptograflar, gizli mesajları "sahte rasgelelik" ile gizleyerek gizler - bu şekilde şifrelenen bir mesaj, herhangi bir kulak misafiri için rastgele bir sayılar karmaşası gibi görünür, ancak yine de amaçlanan alıcı tarafından kodu çözülebilir. Ancak sözde kulak misafiri birinin kodu çözmeyi çok zor bulacağından nasıl emin olabilirsiniz?

Karmaşıklık teorisinin devreye girdiği yer burasıdır. Günümüzde en yaygın şekilde kullanılan şifreleme yöntemlerinin tümü, görünüşte zor olan NP problemlerine dayanmaktadır — mesajın şifresini çözmek için, bir saldırganın sorunu çözmek için henüz keşfedilmemiş hızlı bir algoritmaya ihtiyacı olacaktır. Bu yöntemlerin gerçekten güvenli olduğunu kanıtlamak için yapmanız gereken tek şey P ≠ NP olduğunu kanıtlamaktır. Sipser, kanıt olmadan, yapabileceğiniz tek şeyin "sırrı saklamaya çalıştığınız kişinin sizden daha iyi bir matematikçi olmamasını ummak" olduğunu söyledi.

Kendi başına büyüleyici olsa da, kriptografi, Rudich ve Impagliazzo'yu ilk kez alana çeken kendine gönderme yapan argümanlardan çok uzak görünüyordu. Ancak Rudich, devre karmaşıklığı yaklaşımının neden duraksadığını anlamaya çalışırken, iki konunun birbirinden o kadar da uzak olmadığını fark etmeye başladı. Araştırmacıların, P ≠ NP'nin Gödel'in ünlü "bu ifade kanıtlanamaz" önermesini anımsatan kendi kendini alt eden bir karaktere sahip olduğunu kanıtlama girişimlerinde benimsedikleri strateji - ve kriptografi bunun nedenini açıklamaya yardımcı olabilir. Razborov, Rusya'da da aynı sıralarda benzer bir bağlantı keşfetti. Bunlar, doğal kanıtlar bariyerinin tohumlarıydı.

Doğal kanıtlar bariyerinin kalbindeki gerilim, yüksek karmaşıklıktaki işlevleri düşük karmaşıklıktaki işlevlerden ayırma görevinin, gerçek rasgeleliği mesajları şifrelemek için kullanılan sözde rasgelelikten ayırma görevine benzer olmasıdır. P ≠ NP'yi kanıtlamak için yüksek karmaşıklıktaki fonksiyonların düşük karmaşıklıktaki fonksiyonlardan kategorik olarak farklı olduğunu göstermek istiyoruz. Ancak kriptografinin güvenliğinden emin olmak için sözde rasgeleliğin rasgelelikten ayırt edilemez olmasını da isteriz. Belki iki türlü de olamayız.

Acımasız Bir Şaka

1994'te Razborov ve Rudich benzer içgörülere ulaştıklarını fark ettiler ve sonuçlarını birleştirmek için birlikte çalışmaya başladılar. İlk olarak, devre karmaşıklığını kullanarak P ≠ NP'yi kanıtlamaya yönelik önceki tüm girişimlerin aynı genel stratejiyi benimsediğini gözlemlediler: NP-tam Boole işlevinin özel bir özelliğini tanımlayın, ardından hesaplaması kolay hiçbir işlevin bu özelliği paylaşamayacağını kanıtlayın. Bu, seçilen NP-tamamlama işlevinin hesaplanmasının gerçekten zor olduğunu gösterecek ve P ≠ NP olduğunu kanıtlayacaktır.

Sipser, Razborov ve diğerleri aynı stratejiyi daha sınırlı sonuçlarını kanıtlamak için başarılı bir şekilde kullandılar ve her durumda, araştırmacıların belirlediği özel özellik çoğu Boole işlevi tarafından paylaşıldı. Razborov ve Rudich, sadece bilinen bir alternatif olmadığı için mülkün geniş çapta paylaşıldığı bu duruma atıfta bulunmak için "doğal kanıt" terimini icat ettiler. Eğer "doğal olmayan" kanıtlar mümkün olsaydı, bunlar çok mantığa aykırı ve adını hak edecek nitelikte olmalıydılar.

Razborov ve Rudich ana sonuçlarını kanıtladılar: P ≠ NP'nin doğal bir kanıtı, hesaplaması kolay ve hesaplaması zor fonksiyonların ne kadar farklı olduğunun çok kapsamlı bir şekilde anlaşılmasını gerektirir ve bu bilgi aynı zamanda kolay tespit için hızlı bir algoritmayı besleyebilir. -to-compute işlevleri, yüzeysel olarak karmaşık olsalar bile. Karmaşıklık teorisyenleri P ≠ NP'nin doğal bir kanıtını bulmayı başarmış olsalardı, keyfi bir doğruluk tablosuna göz atmanın ve karşılık gelen fonksiyonun yüksek veya düşük devre karmaşıklığına sahip olup olmadığını belirlemenin neredeyse yanılmaz bir yolunu keşfederlerdi - çok daha güçlü ve daha genel bir sonuç. kanıtlamak için yola çıktılar.

Carmosino, "Pazarlık ettiğinizden daha fazlasını elde etmekten kendinizi alamıyorsunuz," dedi.

Sanki belirli bir ifadenin gerçekliğini kontrol etmeye çalışmışsınız, ancak her girişiminiz genel amaçlı bir yalan makinesinin taslağına dönüşmüş gibi - gerçek olamayacak kadar iyi görünüyor. Karmaşıklık teorisyenleri için, doğal kanıtların şaşırtıcı gücü aynı şekilde başarıyı daha az olası gösteriyordu. Ancak böyle bir kanıt başarılı olsaydı, devre karmaşıklığı ile sözde rasgelelik arasındaki bağlantı nedeniyle beklenmedik sonuçlar kriptografi için kötü haber olurdu.

Bu bağlantıyı anlamak için, birçok girdi değişkeni içeren bir Boole işlevinin doğruluk tablosundaki çıktı sütununa baktığınızı ve her "doğru"yu 1 ile ve her "yanlış"ı 0 ile değiştirdiğinizi hayal edin:

Boole işlevi yüksek devre karmaşıklığına sahipse, bu uzun çıktı listesi prensip olarak gerçekten rastgele bir 0'lar ve 1'ler dizisinden ayırt edilemez olacaktır - örneğin bir madeni paranın tekrar tekrar atılmasıyla elde edilen. Ancak, işlev düşük devre karmaşıklığına sahipse, karmaşık görünse bile dizenin basit, özlü bir açıklaması olmalıdır. Bu, onu kriptografide kullanılan sözde rasgele dizgilere çok benzer kılar; bunların özlü açıklaması, görünürdeki rasgeleliğin içine gömülmüş gizli mesajdır.

Böylece Razborov ve Rudich'in sonucu, P ≠ NP'nin herhangi bir doğal kanıtının, gizli mesajlar içeren sözde rasgele dizileri gerçekten rastgele olanlardan ayırt edebilen hızlı bir algoritma sağlayacağını gösterdi. Araştırmacıların P ≠ NP'yi kanıtlayarak kurmayı umduklarının tam tersi, güvenli kriptografi imkansız olurdu.

Öte yandan, güvenli kriptografi mümkünse, doğal kanıtlar, güvenli kriptografi için bir ön koşul olan P ≠ NP'yi kanıtlamak için uygun bir strateji değildir. Kısaca doğal kanıt engeli budur. Karmaşıklık teorisyenleri acımasız bir şakanın alıcı tarafındaymış gibi görünüyordu.

Kabanets, "Sertliğe inanıyorsanız, sertliği kanıtlamanın zor olduğuna da inanmalısınız" dedi.

Metaverse içine

P ≠ NP varsayımının çıkarımları ile bunu kanıtlamanın zorluğu arasındaki bağlantı ilgi çekiciydi, ancak saptaması zordu. Her şeyden önce, doğal kanıtlar engeli, P ≠ NP'yi kanıtlamak için yalnızca bir yaklaşımı engelledi. Bir diğeri için, P ≠ NP'yi kanıtlamanın zorluğunu P ≠ NP'nin kendisine değil, güvenli kriptografinin varlığına bağladı - yakından ilişkili ancak tam olarak eşdeğer olmayan bir sorun. Bağlantıyı gerçekten anlamak için, araştırmacıların meta-karmaşıklık konusunda rahat olmaları gerekir.

Williams, "'P ≠ NP olduğu için P ≠ NP olduğunu kanıtlamak zor' şeklinde bir sezgi var" dedi. "Fakat bu sezgiyi anlamlandırmak için bile, P ≠ NP gibi bir şeyi bir hesaplama problemi olarak kanıtlama görevini düşünmeye başlamanız gerekir."

Kabanets'in bir yüksek lisans öğrencisi olarak yaptığı buydu. Ukrayna'da büyümüştü ve Sovyetler Birliği'nin dağılmasından iki yıl sonra bilgisayar bilimleri alanında lisans eğitimini tamamladı. Ardından gelen kargaşada, onu en çok ilgilendiren teorik konuları takip etmek için çok az fırsatı oldu.

Kabanets, "Daha akademik bir şey yapmak istedim," diye hatırladı. "Ayrıca dünyayı görmeyi de merak ediyordum." Lisansüstü eğitim için Kanada'ya taşındı ve burada doğal kanıt engelini öğrendi. Carmosino gibi, Kabanets de sonuçtan etkilenmişti. "Bu bağlantıya sahip olman çok derin görünüyordu," dedi.

2000 yılında, yüksek lisans eğitiminin sonlarına doğru, onunla yaptığı konuşmalarda doğal kanıt engelinin ortaya çıkmaya devam ettiğini fark etti. Jin Yi Cai, o sırada izinli olarak Toronto'yu ziyaret eden bir karmaşıklık teorisyeni. Bariyeri bir barikat olarak değil, bir davet olarak görmeye başladılar - sorunları çözmenin ne kadar zor olduğunu tam olarak araştırmak için bir fırsat. bu kâğıt Bu yeni perspektifi ortaya koydukları, yeni ortaya çıkan meta-karmaşıklık alanındaki en etkili erken çalışmalardan biri olacaktı.

Kabanets ve Cai'nin makalesi, Razborov ve Rudich'in doğal kanıtlar bariyeri formülasyonunda üstü kapalı bir hesaplama sorununun altını çizdi: Bir Boole işlevinin doğruluk tablosu verildiğinde, bunun yüksek veya düşük devre karmaşıklığına sahip olup olmadığını belirleyin. Bunu minimum devre boyutu sorunu veya MCSP olarak adlandırdılar.

MCSP, özlü bir meta-karmaşıklık problemidir: konusu grafik teorisi veya başka bir harici konu değil, karmaşıklık teorisinin kendisi olan bir hesaplama problemidir. Aslında bu, karmaşıklık teorisyenlerini 1980'lerde devre karmaşıklığı yaklaşımını kullanarak P'ye karşı NP'yi ele almaya iten sorunun niceliksel bir versiyonu gibidir: Hangi Boolean fonksiyonların hesaplanması zor, hangileri kolaydır?

Impagliazzo, "Bir MCSP algoritması bulursak, bu, karmaşıklık teorisinde yaptığımız şeyi otomatikleştirmenin bir yolu gibi olur," dedi. "En azından bize işimizi nasıl daha iyi yapacağımız konusunda muazzam bir fikir vermeli."

Karmaşıklık teorisyenleri, bu sihirli algoritmanın onları işsiz bırakmasından endişe etmezler - bunun var olduğunu hiç düşünmezler, çünkü Razborov ve Rudich, yüksek karmaşıklıktaki doğruluk tablolarını düşük karmaşıklıktakilerden ayırt etmek için böyle bir algoritmanın kriptografi yapacağını gösterdi. imkansız. Bu, MCSP'nin muhtemelen zor bir hesaplama sorunu olduğu anlamına gelir. Ama ne kadar zor? Hamilton yolu problemi ve araştırmacıların 1960'larda uğraştığı diğer problemler gibi NP-tam mı?

NP'deki problemler için “ne kadar zor?” genellikle cevaplaması yeterince kolaydır, ancak MCSP tuhaf bir aykırı değer gibi görünüyordu. Kabanets, "Zor gibi görünseler de, bu NP-tam problemler adasıyla bağlantılı olmayan 'ortalıkta dolaşan' çok az problemimiz var" dedi.

Kabanets, kendisinin ve Cai'nin MCSP adını verdikleri sorunu ilk düşünenlerin olmadığını biliyordu. Sovyet matematikçiler, 1950'lerden başlayarak, farklı hesaplama problemlerinin içsel zorluklarını anlamak için çok benzer bir problem üzerinde çalıştılar. Leonid Levin, 1960'ların sonlarında NP-tamlık teorisi haline gelecek olan teoriyi geliştirirken bununla boğuşmuştu, ancak bunun NP-tam olduğunu kanıtlayamadı ve ufuk açıcı makalesini onsuz yayınladı.

Bundan sonra, sorun, Kabanets ve Cai onun doğal kanıtlar bariyeriyle bağlantısını fark edene kadar 30 yıl boyunca çok az ilgi gördü. Kabanets, soruyu kendi başına çözmeyi beklemiyordu - bunun yerine, hesaplama zorluğuyla ilgili bu zor görünen sorunun aslında zor olduğunu kanıtlamanın neden bu kadar zor olduğunu keşfetmek istiyordu.

"Bir anlamda, meta-meta-karmaşıklık," dedi Rahul Santhanam, Oxford Üniversitesi'nde bir karmaşıklık teorisyeni.

Ama sertlik baştan aşağı mıydı, yoksa en azından araştırmacıların MCSP'nin NP-tam olduğunu kanıtlamayı neden başaramadığını anlamanın bir yolu var mıydı? Kabanets, evet, bunun bir nedeni olduğunu keşfetti: Devre karmaşıklığını anlamanın zorluğu, MCSP'nin NP-tamlığını kanıtlamak için bilinen herhangi bir stratejinin önünde bir engel görevi görüyor - devre karmaşıklığını anlamanın zorluğuyla ilgili bir problem. Doğal kanıtlar bariyerinin çarpık, kendi kendini baltalayan mantığı kaçınılmaz görünüyordu.

MCSP'nin NP-tamamlanmamış olması da mümkündür, ancak bu da olası görünmüyor - sorunun daha basit varyantlarının NP-tamamlandığı zaten biliniyor.

Impagliazzo, "Onu incelediğimiz diğer tüm problemlerle doğrudan ilişkilendirecek güzel bir yere sahip değiliz" dedi.

Kabanets, MCSP'nin garip davranışını aydınlatmıştı ama nasıl daha fazla ilerleme kaydedeceğini bilmiyordu. Meta-karmaşıklık araştırması yavaşladı. 16 yıl sonra, araştırmacılar başka bir temel soruyla şaşırtıcı bir bağlantı keşfettiklerinde yeniden gelişecekti: Çoğu zaman yalnızca doğru yanıtı almayı umursarsanız sorunları çözmek ne kadar zor olur?

Dünyalar Savaşı

Günlük problemler için çoğu zaman işe yarayan cevaplar genellikle yeterince iyidir. İşe gidiş gelişlerimizi, örneğin en kötü durum senaryoları için değil, tipik trafik modellerine göre planlıyoruz.

Çoğu karmaşıklık kuramcısını tatmin etmek daha zordur: Yalnızca, olası her girdide doğru yanıtı alan hızlı bir algoritma bulabilirlerse, bir sorunu kolay ilan etmekle yetinirler. Bu standart yaklaşım, sorunları araştırmacıların "en kötü durum" karmaşıklığı dediği şeye göre sınıflandırır. Ancak, çoğu girdide doğru yanıtı alan hızlı bir algoritma varsa, sorunların kolay kabul edildiği bir “ortalama durum” karmaşıklığı teorisi de vardır.

Ayrım, kriptograflar için önemlidir. En iyi algoritmanın başarısız olduğu birkaç inatçı durum dışında, hemen hemen her girdi için çözülmesi kolay bir hesaplama problemi hayal edin. En kötü durum karmaşıklığı teorisi, bunun zor bir problem olduğunu düşünür, ancak kriptografi için işe yaramaz: Sadece bazı mesajlarınızın şifresini çözmek zorsa, ne anlamı var?

NP-tamlığı konusundaki öncü çalışmasından on yıl sonra, ortalama vaka karmaşıklığına ilişkin titiz çalışmayı başlatan aslında Levin'di. Aradan geçen yıllarda, Sovyet yetkilileriyle ters düşmüştü - Komünist parti gençlik grubundaki yurtsever faaliyetleri ara sıra baltalayan saygısız bir baş belasıydı. 1972'de açıkça siyasi nedenlerle doktorası reddedildi.

Impagliazzo, "Genç bir araştırmacı olarak Sovyetler Birliği'nde başarılı olmak için çok inatçı olamazsınız ve Leonid'in inatçı olmadığını hayal etmek zor," dedi.

Levin, 1978'de Amerika Birleşik Devletleri'ne göç etti ve 1980'lerin ortalarında dikkatini ortalama vaka karmaşıklığına çevirdi. O sırada yüksek lisans öğrencisi olan Impagliazzo da dahil olmak üzere teoriyi daha da geliştirmek için başkalarıyla çalışmaya başladı. Ancak ilerleme kaydederken bile Impagliazzo, araştırmacıların sık sık birbirlerini geçiştirdiklerini fark etti. Herkesi aynı noktada buluşturmak istiyordu ve Levin'in makalelerinin özlü olmasıyla ünlü olması da ona yardımcı olmadı. alanı başlattı ortalama vaka karmaşıklığı iki sayfadan azdı.

Impagliazzo, "Leonid'in çalışmasının daha erişilebilir teknik terimlere çevirisini yapacaktım," dedi. Matematiğe dalmadan önce büyük resme kısa, eğlenceli bir genel bakışla başlamaya karar verdi. "Bu tür bir gazeteyi ele geçirdi ve zaten herkesin hatırladığı tek kısım bu."

The kâğıt1995 yılında yayınlanan, anında bir klasik haline geldi. Impagliazzo tuhaf isimler icat etti. beş dünya farklı derecelerde hesaplama sertliği ve farklı şifreleme yetenekleri ile ayırt edilir. Bu dünyalardan birinde yaşıyoruz ama hangisi olduğunu bilmiyoruz.

Impagliazzo'nun makalesi çıktığından beri, araştırmacılar onun minyatür çoklu evreninin bazı kısımlarını ortadan kaldırmayı hayal ettiler - bazı dünyaların hiç de mümkün olmadığını kanıtlayarak olasılıklar alanını daralttılar. İki dünya özellikle cezbedici hedeflerdir: P ≠ NP olsa bile kriptografinin imkansız olduğu yerler.

Heuristica adı verilen bu dünyalardan birinde, tüm NP-tamamlanmış problemlerin çoğu girdide çözülmesi kolaydır, ancak hızlı algoritmalar ara sıra hata yapar, bu nedenle bu problemler, en kötü durum karmaşıklığı teorisinin standartlarına göre hala zor kabul edilir. Bu, kriptografinin imkansız olduğu bir dünya çünkü neredeyse her kod kolayca kırılabilir. Pessiland adı verilen diğer dünyada, kriptografi farklı bir nedenden dolayı imkansızdır: Ortalama durum anlamında her problem zordur, ancak bir mesajı şifrelemek, onu hedeflenen alıcı için bile okunamaz hale getirir.

Bu iki dünyanın meta-karmaşıklık sorunlarıyla yakından bağlantılı olduğu ortaya çıktı - özellikle, Heuristica'nın kaderi, MCSP'nin NP-tamamlanıp tamamlanmadığına dair uzun süredir devam eden soruyla bağlantılı. Uzun zaman önce Kabanets'i büyüleyen ve Levin'i şaşırtan soru sadece merak değil: Bütün bir dünya tehlikede.

Heuristica'yı ekarte etmek için, araştırmacıların en kötü durum ve ortalama durum karmaşıklığı arasındaki ayrımı ortadan kaldırmaları gerekecek - yani, çoğu girdide bir NP-tam problemini doğru bir şekilde çözen herhangi bir varsayımsal algoritmanın gerçekten çözebileceğini kanıtlamaları gerekecekti. her durumda. En kötü durumdan ortalama duruma indirgeme olarak adlandırılan bu tür bir bağlantının belirli problemler için var olduğu biliniyor, ancak bunların hiçbiri NP-tam değil, bu nedenle bu sonuçlar daha genel bir şey ima etmiyor. Heuristica'yı ortadan kaldırmak, kriptografları, P ≠ NP şeklindeki tek varsayıma dayalı güvenli şifreleme hayalini gerçekleştirmenin yarısına götürecektir.

Ancak bir dünyayı yok etmek küçük bir başarı değil. 2003 yılında, iki karmaşıklık teorisyeni gösterdi bilinen NP-tam problemler için en kötü durumdan ortalama duruma azalmaları kanıtlamaya yönelik mevcut yaklaşımların, bu tür kanıtların muhtemelen mümkün olmadığını öne sürerek tuhaf sonuçlara işaret edeceği.

Araştırmacıların başka bir yaklaşım bulması gerekecek ve şimdi MCSP'nin ihtiyaç duydukları problem olabileceğini düşünüyorlar. Ancak bu, on yıldan fazla bir süre netlik kazanmayacaktı. Bağlantının ilk görüntüsü, Marco Carmosino'nun doğal kanıtlar engeline duyduğu ısrarlı hayranlıktan ortaya çıktı.

Carmosino, meta-karmaşıklık araştırmasıyla ilk kez bir yüksek lisans öğrencisiyken karşılaştı. 2013 kağıt Kabanets ve diğer dört araştırmacı tarafından, Kabanets'in on yıldan fazla bir süre önce öncülük ettiği doğal kanıtlar bariyerine yaklaşımı daha da geliştirdi. Sadece Razborov ve Rudich'in klasik makalesinden öğrenecek daha çok şey olduğuna olan inancını güçlendirdi.

Carmosino, "O sırada o gazeteye takıntılıydım," dedi. "Hiçbir şey değişmedi."

Saplantı nihayet, zamanının çoğunu Impagliazzo, Kabanets ve Antonina Kolokolova2013 raporunda Kabanets ile işbirliği yapan Newfoundland Memorial Üniversitesi'nde bir karmaşıklık teorisyeni. Carmosino, üçüyle daha önce bir kez çalışmıştı ve bu başarılı işbirliği, ona kendisini en çok etkileyen konuyla ilgili sorularla doldurma güvenini verdi.

Kabanets, "İnsanları iyi bir şekilde rahatsız ediyordu" diye hatırladı.

İlk başta, Carmosino'nun Razborov ve Rudich'in doğal kanıtlar bariyeri hakkındaki makalesinde ortaya çıkan MCSP versiyonu için NP-tamlığını kanıtlamak için yeni fikirleri vardı. Ancak bu fikirler sonuç vermedi. Bunun yerine, Impagliazzo'nun gelişigüzel bir açıklaması, dört araştırmacının, doğal kanıtlar bariyerinin, kimsenin fark etmediği kadar güçlü algoritmalar sağlayabileceğini fark etmelerini sağladı - barikata kazınmış gizli bir harita vardı.

İçinde 2016 kağıt, dört araştırmacı, belirli bir tür ortalama durum MCSP algoritmasının, rastgele görünen rakam dizilerinde gizlenmiş kalıpları tanımlamak için en kötü durum algoritması oluşturmak için kullanılabileceğini kanıtladı - bilgisayar bilimcilerinin "öğrenme" olarak adlandırdığı bir görev. Bu çarpıcı bir sonuç çünkü sezgisel olarak öğrenmek, bir MCSP algoritması tarafından gerçekleştirilen ikili sınıflandırma görevinden (yüksek karmaşıklık veya düşük karmaşıklık) daha zor görünüyor. Ve şaşırtıcı bir şekilde, bir görevin en kötü durum karmaşıklığını diğerinin ortalama durum karmaşıklığına bağladı.

Impagliazzo, "Böyle bir bağlantının var olacağı açık değildi," dedi.

MCSP için hızlı bir algoritma, genel Boole devreleri için tamamen varsayımsaldır: Aksi yöndeki tüm kanıtlara rağmen, MCSP'nin kolay bir hesaplama sorunu olduğu ortaya çıkmadıkça var olamaz ve bu, dört araştırmacının makalesinin ima ettiği öğrenme algoritmasının olduğu anlamına gelir. eşit derecede varsayımsal.

Ancak MCSP'nin bazı daha basit sürümleri için - devrelerde belirli kısıtlamalar olduğunda yüksek karmaşıklıktaki doğruluk tablolarını düşük karmaşıklıktaki tablolardan ayırt etmek - hızlı algoritmalar uzun yıllardır bilinmektedir. Carmosino, Impagliazzo, Kabanets ve Kolokolova'nın makalesi, bu algoritmaların benzer şekilde kısıtlı ancak yine de araştırmacıların daha önce bu kadar titiz bir teorik düzeyde anladıklarından daha güçlü olan öğrenme algoritmalarına dönüştürülebileceğini gösterdi.

Ilango, "Bir şekilde, kendi kendine gönderme yapan lezzetleri, daha standart problemlerle yapamayacağınız şeyleri yapmanızı sağlıyor" dedi.

Sonuç, diğer konularda çalışan karmaşıklık teorisyenlerinin dikkatini çekti. Aynı zamanda, meta-karmaşıklık ile ortalama vaka karmaşıklığı arasında önümüzdeki yıllarda ortaya çıkacak olan daha fazla bağlantının bir önizlemesiydi.

Hepsinden önemlisi, araştırmacıların ilk başta yalnızca ilerlemelerini engelliyormuş gibi görünen engeller hakkında basit sorular sorarak ne kadar ileri gidebileceklerinin bir kanıtıydı.

Impagliazzo, "Bu tür bir ikilik, en azından son 30 veya 40 yıllık karmaşıklık boyunca bir temadır" dedi. "Engeller genellikle fırsatlardır."

Kısmi kredi

İlerleme, Carmosino ve meslektaşlarının makalelerini yayınlamalarından bu yana geçen yıllarda hızlandı.

Kolokolova, "Yeni şeyler oluyor," dedi. "Gerçekten çok parlak, çok sayıda genç araştırmacı var."

Ilango, bu genç araştırmacılardan biri — lisansüstü okulunun ilk üç yılında, iki yönlü bir strateji kullanarak MCSP NP-tamamlandığını kanıtlama gibi göz korkutucu açık bir soruna saldırdı: basit sürümler devre karmaşıklığı araştırmacılarının 1980'lerde P'ye karşı NP'ye saldırırken yaptığı gibi, MCSP'nin daha karmaşık versiyonlar, sezgisel olarak daha zor görünen ve bu nedenle zor olduğunu kanıtlamak belki de daha kolaydır.

Ilango, meta-karmaşıklığa olan ilgisini şuna borçludur: Eric AllenRutgers Üniversitesi'nde bir karmaşıklık teorisyeni ve 2000'lerde ve 2010'ların başında meta-karmaşıklık üzerinde çalışmaya devam eden birkaç araştırmacıdan biri. Ilango, "Onun coşkusu bulaşıcıydı," dedi.

Allender'dan ilham alan bir diğer genç araştırmacı ise Shuichi Hirahara, şimdi Tokyo'daki Ulusal Bilişim Enstitüsü'nde profesör. Hirahara, 2018'de hâlâ yüksek lisans öğrencisiyken, Carmosino ve ortak yazarlarının keşfettiği meta-karmaşıklık ile ortalama vaka karmaşıklığı arasındaki ilişkinin gerçek boyutunu ortaya çıkardı. Bu dört araştırmacı, bir problemin (MCSP) ortalama durum karmaşıklığı ile bir diğerinin en kötü durum karmaşıklığı olan Boole öğrenmesi arasında bir bağlantı bulmuştu. Hirahara tekniklerini daha da geliştirdi türetmek MCSP için en kötü durumdan ortalama duruma indirgeme. Elde ettiği sonuç, Carmosino ve meslektaşlarının düşündüğü gibi varsayımsal bir ortalama durum MCSP algoritmasının aslında MCSP'nin biraz farklı bir sürümünü herhangi bir hata yapmadan çözecek kadar güçlü olacağını ima ediyor.

Hirahara'nın sonucu heyecan verici çünkü birçok araştırmacı, en kötü durumdan ortalama duruma indirgemenin bilindiği diğer tüm sorunların aksine, MCSP'nin NP-tam olduğundan şüpheleniyor. Hirahara'nın sonuçlarını tüm ortalama durum algoritmalarını kapsayacak şekilde genişletebilirlerse ve ardından MCSP'nin NP-tam olduğunu kanıtlarlarsa, bu bizim Heuristica'da yaşamadığımızı kanıtlar.

Santhanam, "Bu gerçekten dünyayı sarsan bir sonuç olur," dedi.

MCSP'nin NP-tamamlandığını kanıtlamak zor bir görev gibi görünebilir - sonuçta, soru 50 yılı aşkın bir süredir açıktı. Ama sonra bir buluş Geçen yıl Hirahara tarafından geliştirilen araştırmacılar, birkaç yıl önce herkesin umacağından çok daha yakın.

Hirahara, her doğruluk tablosundaki belirli girişleri göz ardı ettiğiniz, kısmi MCSP adı verilen problemin bir varyantı için NP-tamlığını kanıtladı. Kanıtı, kısmi MCSP'nin gizli paylaşım adı verilen kriptografik bir tekniği içeren görünüşte ilgisiz bir soruna eşdeğer olduğunu göstermek için Ilango tarafından geliştirilen yöntemlere dayanıyordu. Bu, şifrelenmiş bir mesajı birçok kişi arasında bölmenin bir yoludur, böylece yalnızca belirli bir kısmı birlikte çalışırsa kodu çözülebilir.

Kriptografideki herhangi bir gerçek uygulama için, bu kesri önceden bilmek istersiniz, ancak ekstra kriptografik hilelerin yardımıyla, kaç kişinin işbirliği yapması gerektiğini anlamanın zor olduğu sinir bozucu bir senaryo oluşturabilirsiniz. Hirahara, bu uydurulmuş kriptografik problemin NP-tam olduğunu kanıtlamanın bir yolunu buldu ve ardından kanıtın, kısmi MCSP'nin de NP-tamlığını ima ettiğini gösterdi.

Bu sonuç, araştırmacılara meta-karmaşıklık konusunda Hirahara'nın önceki çalışmasından daha fazla enerji verdi ve diğer araştırmacılar da dikkat çekti - karmaşıklık teorisyeni ve blog yazarı Lance Fortnow bunu yılın sonucu. Bunun nedeni, hesaplama problemlerinin bu tür "kısmi fonksiyon" versiyonlarının üstesinden gelmenin, diğer NP-tamlık ispatlarında önemli bir ara adım olmasıdır.

Williams, "Bu harika bir iş," dedi. "Herkes bu kısmi problemlerin kabaca tam problemle aynı zorlukta olduğunu düşündü."

MCSP'nin tam sürümü için NP-tamlığının kanıtlanmasına yönelik engeller devam etmektedir. Ancak hiçbiri tamamen yeni bir araç setine ihtiyaç duyulduğunu düşündüren türden engeller değildir - bilinen teknikleri birleştirmenin doğru yolunu bulma meselesi olabilir. Bir ispat, karmaşıklık teorisi var olduğu sürece sınıflandırmaya direnen birkaç problemden birinin durumunu nihayet çözecektir. Levin e-postayla şunları yazdı: "Onu göremediğim için aptal olduğumu göstermek beni küçük düşürür :-)."

Eksik Parçalar

MCSP, büyük bir atılımı teşvik eden tek meta-karmaşıklık sorunu bile değil. 2020'de Cornell Tech kriptografı Rafael Geçidi ve onun yüksek lisans öğrencisi Yanyi Liu bir bağlantı keşfetti farklı bir meta-karmaşıklık sorunu ile Heuristica ile Impagliazzo'nun dünyalarının en kötüsü olan Pessiland arasındaki sınırı tanımlayan temel bir kriptografik protokol arasında (burada NP-tam problemler ortalama durum anlamında zordur, ancak kriptografi hala imkansızdır). Bu, üzerinde çalıştıkları sorunu, Pessiland'a yapılacak bir saldırı için birincil aday haline getiriyor ve onların daha yeni çalışma Heuristica'ya karşı da işe yarayabileceğini gösterir.

Pass, "Yapbozun farklı parçaları eksik," dedi. "Bana göre bu alanların bu kadar yakından bağlantılı olması büyülü bir şey."

Hirahara, Impagliazzo'nun 30 yıl önce yarattığı dünyaları ayıklamak isteyen araştırmacıları hâlâ bekleyen zorluklar konusunda uyarıyor. "Bir noktada Heuristica ve Pessiland'ın eleneceğini söylemek isterdim ama ne kadar yakın olduğumuzdan emin değilim" dedi.

Pek çok araştırmacı, en büyük zorluğun, iki farklı ortalama vaka karmaşıklığı modeli arasındaki görünüşte zararsız bir uçurumu kapatmak olacağını düşünüyor. Kriptograflar genellikle her iki yönde de hata yapan ortalama durum algoritmalarını inceler, ara sıra rasgele dizileri sözde rasgele olarak yanlış etiketler ve bunun tersi de geçerlidir. Bu arada, Hirahara'nın en kötü durumdan ortalama duruma indirgemesi, yalnızca ilk tür hatayı yapan ortalama durum algoritmaları için çalışır. Bunun gibi ince ayrımlar, karmaşıklık teorisinde büyük farklar yaratabilir. Ancak bu ve diğer pek çok engele rağmen, Allendere temkinli bir iyimserlik havası vermekten kendini alamaz.

"Kendime çok fazla inanan olmamaya çalışıyorum çünkü hiçbir şeyin işe yaramadığına dair oldukça köklü bir geçmiş performans var" dedi. "Ama gerçekten heyecan verici pek çok gelişme görüyoruz - engel gibi görünen şeyleri aşmanın yolları."

Araştırmacıların P'ye karşı NP sorusunu cevaplamak için verdikleri mücadeleden öğrendikleri bir ders varsa - ya da sadece anlasalar bile - o da karmaşıklık teorisinin kendisinin karmaşık olduğudur. Ancak bu meydan okuma, arayışı bu kadar ödüllendirici yapan şeydir.

Carmosino, "Aslında bu kadar zor olması harika," dedi. "Asla sıkılmayacağım."

Editörün notu: Scott Aaronson, Quanta Dergisi'S danışma kurulu.