Călătoria de 50 de ani a teoriei complexității către limitele cunoașterii | Revista Quanta

În prima săptămână a semestrului de toamnă din 2007, Marco Carmosino s-a târât la o clasă de matematică necesară pentru toate specializările în informatică de la Universitatea din Massachusetts, Amherst. Carmosino, student în doi ani, se gândea să renunțe la facultate pentru a crea jocuri video. Apoi profesorul a pus o întrebare simplă care i-ar schimba cursul vieții: De unde știi că matematica funcționează de fapt?

„Asta m-a făcut să mă ridic și să fiu atent”, și-a amintit Carmosino, acum un informatician teoretic la IBM. S-a înscris la un seminar opțional despre opera lui Kurt Gödel, ale cărui argumente autoreferențiale amețitoare au expus pentru prima dată limitele raționamentului matematic și au creat fundamentul pentru toate lucrările viitoare privind limitele fundamentale ale calculului. Era mult de luat.

„Nu am înțeles 100%”, a spus Carmosino. „Dar știam că vreau.”

Astăzi, chiar și cercetătorii experimentați găsesc puțină înțelegere atunci când se confruntă cu întrebarea centrală deschisă în informatica teoretică, cunoscută sub numele de problema P versus NP. În esență, această întrebare se întreabă dacă multe probleme de calcul considerate mult timp extrem de dificile pot fi de fapt rezolvate cu ușurință (printr-o scurtătură secretă pe care nu am descoperit-o încă) sau dacă, după cum bănuiesc majoritatea cercetătorilor, sunt cu adevărat dificile. În joc este nimic mai puțin decât natura a ceea ce este cunoscut.

În ciuda deceniilor de eforturi ale cercetătorilor în domeniul teoriei complexității computaționale - studiul unor astfel de întrebări despre dificultatea intrinsecă a diferitelor probleme - o soluție la întrebarea P versus NP a rămas evazivă. Și nici măcar nu este clar de unde ar trebui să înceapă o dovadă.

„Nu există nicio foaie de parcurs”, a spus Michael Sipser, un veteran teoretician al complexității de la Institutul de Tehnologie din Massachusetts, care a petrecut ani de zile luptându-se cu problema în anii 1980. „Parcă ai merge în pustie.”

Se pare că a demonstra că problemele de calcul sunt greu de rezolvat este în sine o sarcină grea. Dar de ce este atât de greu? Și cât de greu este? Carmosino și alți cercetători din subdomeniul meta-complexității reformulează întrebări ca aceasta ca probleme de calcul, propulsând domeniul înainte prin întoarcerea lentilei teoriei complexității înapoi asupra lor.

„S-ar putea să te gândești: „OK, e cam grozav. Poate că teoreticienii complexității au înnebunit”, a spus Rahul Ilango, un student absolvent la MIT care a produs unele dintre cele mai interesante rezultate recente în domeniu.

Studiind aceste întrebări care privesc spre interior, cercetătorii au aflat că duritatea dovedirii durității computaționale este strâns legată de întrebări fundamentale care pot părea la început fără legătură. Cât de greu este să reperezi modele ascunse în date aparent aleatorii? Și dacă există probleme cu adevărat grele, cât de des sunt ele grele?

„A devenit clar că meta-complexitatea este aproape de inima lucrurilor”, a spus Scott Aaronson, un teoretician al complexității la Universitatea din Texas, Austin.

Aceasta este povestea traseului lung și sinuos care a condus cercetătorii de la problema P versus NP la meta-complexitate. Nu a fost o călătorie ușoară – poteca este plină de viraj false și blocaje și se întoarce pe sine din nou și din nou. Cu toate acestea, pentru cercetătorii de meta-complexitate, acea călătorie într-un peisaj neexplorat este propria sa recompensă. Începeți să puneți întrebări aparent simple, spuse Valentine Kabanets, un teoretician al complexității la Universitatea Simon Fraser din Canada și „nu ai idee unde vei ajunge”.

Necunoscute cunoscute

Problema P versus NP își datorează numele lipsit de strălucire obiceiului teoreticienilor în complexitate de a sorta problemele computaționale în linii mari.clase de complexitate” cu etichete care sugerează simboluri ticker Nasdaq. O problemă de calcul este una care, în principiu, poate fi rezolvată printr-un algoritm - o listă de instrucțiuni precis specificată. Dar nu toți algoritmii sunt la fel de utili, iar variația dintre algoritmi sugerează diferențe fundamentale între problemele din diferite clase. Provocarea pentru teoreticienii complexității este de a transforma aceste indicii în teoreme riguroase despre relațiile dintre clasele de complexitate.

Aceste relații reflectă adevăruri imuabile despre calcul, care depășesc cu mult orice tehnologie specifică. „Este ca și cum ai descoperi legile universului”, a spus Kabanets.

„P” și „NP” sunt cei mai faimoși doi membri ai a menajerie în creștere a sutelor de clase de complexitate. În linii mari, P este clasa de probleme care pot fi rezolvate cu ușurință, cum ar fi alfabetizarea unei liste. NP este clasa de probleme cu soluții ușor de verificat, cum ar fi puzzle-urile sudoku. Deoarece toate problemele ușor de rezolvat sunt, de asemenea, ușor de verificat, problemele din P sunt și în NP. Dar unele probleme NP par greu de rezolvat - nu poți intui imediat soluția unui puzzle sudoku fără a încerca mai întâi multe posibilități. S-ar putea ca această duritate aparentă să fie doar o iluzie - că există un singur truc simplu pentru a rezolva orice problemă ușor de verificat?

Dacă da, atunci P = NP: Cele două clase sunt echivalente. Dacă este cazul, trebuie să existe un algoritm care să facă trivială rezolvarea de puzzle-uri sudoku enorme, optimizarea rutelor de transport maritime globale, ruperea criptării de ultimă generație și automatizarea dovezilor teoremelor matematice. Dacă P ≠ NP, atunci multe probleme de calcul care sunt rezolvabile în principiu vor rămâne în practică pentru totdeauna dincolo de înțelegerea noastră.

Cercetătorii s-au îngrijorat de limitele raționamentului matematic formal cu mult înainte ca problema P versus NP să fie formulată pentru prima dată - într-adevăr, cu mult înainte de începutul informaticii moderne. În 1921, luptându-se cu aceeași întrebare care avea să-i capteze atenția lui Carmosino aproape un secol mai târziu, matematicianul David Hilbert a propus un program de cercetare pentru fundamentarea matematicii în certitudine absolută. El a sperat să plece de la câteva ipoteze simple, numite axiome, și să obțină o teorie matematică unificată care să îndeplinească trei criterii cheie.

Prima condiție a lui Hilbert, consistența, a fost cerința esențială ca matematica să fie liberă de contradicții: dacă două afirmații contradictorii ar putea fi dovedite pornind de la aceleași axiome, întreaga teorie ar fi de nesalvat. Dar o teorie ar putea fi lipsită de contradicții și totuși limitată în acoperirea ei. Aceasta a fost motivația pentru a doua condiție a lui Hilbert, completitudinea: cerința ca toate afirmațiile matematice să fie fie adevărate dovedit, fie false. Al treilea criteriu al său, determinabilitatea, a cerut o procedură mecanică neechivocă pentru a determina dacă orice afirmație matematică era adevărată sau falsă. Adresându-se la o conferință din 1930, Hilbert a declarat: „Sloganul nostru va fi „Trebuie să știm, vom ști”.

Doar un an mai târziu, Gödel a dat prima lovitură visului lui Hilbert. El s-au dovedit că o afirmație auto-învinsă precum „această afirmație este de nedemonstrat” ar putea fi derivată din orice set adecvat de axiome. Dacă o astfel de afirmație este într-adevăr de nedemonstrat, teoria este incompletă, dar dacă este demonstratabilă, teoria este inconsecventă - un rezultat și mai rău. În aceeași lucrare, Gödel a demonstrat, de asemenea, că nicio teorie matematică nu și-ar putea dovedi propria consistență.

Cercetătorii încă au sperat că o viitoare teorie a matematicii, deși neapărat incompletă, s-ar putea dovedi totuși decidabilă. Poate că ei ar putea dezvolta proceduri care să identifice toate afirmațiile dovedibile, ținând în același timp departe de propoziții supărătoare precum cea a lui Gödel. Necazul era că nimeni nu știa cum să raționeze aceste proceduri ipotetice.

Apoi, în 1936, un student absolvent de 23 de ani, pe nume Alan Turing, a reformulat condiția de decidebilitate a lui Hilbert în limbajul de calcul necunoscut atunci și i-a dat o lovitură fatală. Turing a formulat un model matematic - acum cunoscut sub numele de Mașină de întărire — care ar putea reprezenta toți algoritmii posibili și a arătat că, dacă ar exista procedura lui Hilbert, s-ar încadra în acest model. Apoi a folosit metode auto-referențiale precum cea a lui Gödel dovedi existența unor declarații indecidabile — sau, echivalent, probleme necalculabile pe care niciun algoritm nu le-ar putea rezolva.

Programul lui Hilbert era în ruine: vor exista pentru totdeauna limite fundamentale pentru ceea ce ar putea fi demonstrat și ce ar putea fi calculat. Dar pe măsură ce computerele au evoluat de la abstracții teoretice la mașini reale, cercetătorii și-au dat seama că simpla distincție a lui Turing între problemele rezolvabile și cele de nerezolvat a lăsat multe întrebări fără răspuns.

Până în anii 1960, oamenii de știință în computer au dezvoltat algoritmi rapizi pentru a rezolva unele probleme, în timp ce pentru altele, singurii algoritmi cunoscuți erau extrem de lenți. Ce se întâmplă dacă întrebarea nu ar fi doar dacă problemele sunt rezolvabile, ci cât de greu sunt de rezolvat?

„Apare o teorie bogată și nu mai știm răspunsurile”, a spus Carmosino.

Căi divergente

Pentru a ilustra cât de perplexe pot fi întrebările despre duritate, să luăm în considerare o pereche de probleme strâns legate care implică grafice. Acestea sunt rețele de puncte, numite noduri, conectate prin linii, numite muchii. Informaticii le folosesc pentru a modela totul de la calcul cuantic la fluxul de trafic.

Să presupunem că vi se oferă un grafic și vi se cere să găsiți ceva numit cale hamiltoniană - o rută care trece prin fiecare nod exact o dată. Această problemă este clar rezolvabilă în principiu: există doar un număr finit de căi posibile, așa că dacă toate celelalte nu reușesc, le puteți verifica pe fiecare. Este în regulă dacă există doar câteva noduri, dar chiar și pentru grafice puțin mai mari, numărul de posibilități scapă de sub control, făcând rapid acest algoritm simplu inutil.

Există algoritmi de cale hamiltonieni mai sofisticați care duc o luptă mai bună, dar timpul necesar algoritmilor pentru a rezolva problema crește invariabil exponențial odată cu dimensiunea graficului. Graficele nu trebuie să fie foarte mari înainte ca chiar și cei mai buni cercetători de algoritmi au descoperit că nu pot găsi o cale „într-o perioadă rezonabilă de timp”, a spus Russell Impagliazzo, un teoretician al complexității la Universitatea din California, San Diego. „Și prin „o perioadă rezonabilă de timp”, vreau să spun „înainte de a se termina universul”.

Problema drumului hamiltonian are o altă proprietate interesantă. Dacă cineva pretinde că a găsit o cale hamiltoniană pe un anumit grafic, puteți verifica rapid dacă soluția este validă, chiar dacă graficul este foarte mare. Tot ce trebuie să faceți este să urmați calea și să bifați nodurile unul câte unul, verificând pentru a vă asigura că nu ați bifat niciun nod de două ori. Dacă nu lipsesc niciun nod la sfârșit, atunci calea este hamiltoniană.

Timpul necesar rulării acestui algoritm de verificare a soluției este proporțional cu dimensiunea graficului. Aceasta îl plasează în categoria mai largă a algoritmilor polinomiali, ale căror timpi de rulare cresc ca funcții polinomiale ale dimensiunii graficului. Creșterea polinomială este blândă în comparație cu creșterea exponențială, astfel încât algoritmii polinomiali rămân viabili chiar și pe grafice mari. „Este mult mai eficient”, a spus Carmosino.

Problema drumului hamiltonian are o asimetrie puternică: puteți verifica o soluție corectă folosind un algoritm polinomial rapid, dar pentru a găsi o soluție veți avea nevoie de un algoritm exponențial lent. Această asimetrie poate să nu pară surprinzătoare – este mai ușor să recunoști o capodopera artistică decât să creezi una, mai ușor să verifici o demonstrație matematică decât să dovedești o nouă teoremă – totuși nu toate problemele de calcul au acest caracter asimetric. De fapt, o problemă foarte asemănătoare cu găsirea căilor hamiltoniene se comportă destul de diferit.

Să presupunem că vi se oferă din nou un grafic, dar acum vi se cere să găsiți o „cale euleriană” care traversează fiecare margine exact o dată. Din nou, există un algoritm polinom pentru verificarea posibilelor soluții, dar de data aceasta există și un algoritm polinom pentru rezolvarea problemei. Nicio asimetrie aici. În teoria complexității, unele căi par mai ușor de găsit decât altele.

Atât problema drumului hamiltonian, cât și problema căii euleriene sunt în clasa de complexitate NP, definită pentru a include toate problemele ale căror soluții pot fi verificate prin algoritmi polinomi. Problema căii euleriene se încadrează, de asemenea, în clasa P, deoarece un algoritm polinomial o poate rezolva, dar după toate aparențele, acest lucru nu este adevărat pentru problema căii hamiltoniene. De ce ar trebui aceste două probleme grafice, atât de superficial similare, să difere atât de dramatic? Aceasta este esența problemei P versus NP.

Universal greu

La început, clasele de complexitate păreau categorii convenabile pentru sortarea problemelor care erau similare, dar nu erau direct legate - nimeni nu bănuia că găsirea căilor hamiltoniene are vreo legătură cu alte probleme de calcul dificile.

Apoi, în 1971, la un an de la mutarea la Universitatea din Toronto, după ce i s-a refuzat mandatul în Statele Unite, teoreticianul complexității Stephen Cook a publicat un rezultat extraordinar. El a identificat o anumită problemă NP cu o caracteristică ciudată: dacă există un algoritm polinom care poate rezolva acea problemă, poate rezolva și orice altă problemă din NP. Problema „universală” a lui Cook, se părea, era o coloană singură care susținea clasa de probleme aparent dificile, separându-le de problemele ușoare de mai jos. Rezolvați acea problemă și restul NP se va prăbuși.

Cook a bănuit că nu există un algoritm rapid pentru problema lui universală și a spus la fel de mult la jumătatea lucrării, adăugând: „Simt că merită să depuneți un efort considerabil pentru a încerca să demonstrăm această presupunere”. „Efort considerabil” s-ar dovedi a fi o subestimare.

Cam în același timp, un student absolvent din Uniunea Sovietică a numit Leonid Levin a dovedit a rezultat similar, cu excepția faptului că a identificat mai multe probleme universale diferite. În plus, teoreticianul american al complexității Richard Karp s-au dovedit că proprietatea de universalitate identificată de Cook (și Levin, deși Karp și Cook nu au știut de opera lui Levin decât ani mai târziu) a fost ea însăși aproape universală. Aproape fiecare problemă NP fără un algoritm polinom cunoscut - adică aproape fiecare problemă ușor de verificat care părea dificilă - avea aceeași proprietate, care a devenit cunoscută sub numele de NP-completitudine.

Aceasta înseamnă toate problemele NP-complete — problema drumului hamiltonian, sudoku și mii al altora — sunt echivalente într-un sens precis. „Aveți toate aceste sarcini naturale diferite și toate, în mod magic, se dovedesc a fi aceeași sarcină”, a spus Ilango. „Și încă nu știm dacă aceeași sarcină este posibilă sau nu.”

Soluționarea dificultății oricărei probleme NP-complete ar fi suficientă pentru a rezolva întrebarea P versus NP. Dacă P ≠ NP, distincția dintre problemele ușoare și cele dificile este susținută de mii de coloane care sunt toate la fel de puternice. Dacă P = NP, întregul edificiu se clătina în pragul prăbușirii, așteptând doar să cadă o singură bucată.

Cook, Levin și Karp unificaseră ceea ce păreau a fi multe probleme fără legătură. Acum tot ce trebuiau să facă teoreticienii complexității a fost să rezolve o singură problemă: P = NP sau nu?

Cincizeci de ani mai târziu, întrebarea rămâne fără răspuns. Kabanets a asemănat raționamentul cu privire la limitele calculului cu supravegherea unui teritoriu vast, fără nici un sens al imaginii de ansamblu. O ființă cu o putere de calcul nelimitată ar putea privi în jos de pe un vârf de munte și să cuprindă întregul peisaj deodată, dar simplii muritori nu pot conta pe un asemenea avantaj. „Aceia dintre noi de la poalele muntelui poate încerca să sară în sus și în jos pentru o vedere mai bună”, a spus el.

Să presupunem că P = NP. Pentru a dovedi acest lucru, cercetătorii ar trebui să găsească un algoritm rapid pentru o problemă NP-completă, care ar putea fi ascunsă într-un colț obscur al acelui peisaj vast. Nu există nicio garanție că o vor găsi în curând: teoreticienii complexității au făcut-o ocazional a descoperit algoritmi ingenioși pentru probleme aparent grele (deși nu NP-complete) numai după decenii de muncă.

Acum să presupunem că P ≠ NP. Să demonstrezi asta pare și mai greu. Teoreticienii complexității ar trebui să stabilească că nu ar putea exista niciun algoritm rapid, care să anticipeze și să zădărnicească în mod eficient eforturile tuturor viitorilor cercetători.

A nu ști de unde să încep face parte din problemă. Dar nu e ca și cum cercetătorii nu au încercat. De-a lungul deceniilor, au atacat problema din mai multe unghiuri și au găsit calea blocată la fiecare cotitură. „Este unul dintre cele mai flagrante adevăruri din informatica teoretică”, a spus Carmosino. „Când ai un fenomen care este atât de durabil, vrei niște explicații.”

Până în ultimul an de facultate al lui Carmosino, curiozitatea lui îl condusese de la Gödel la un curs de absolvire în teoria complexității. A fost surprins să-și dea seama că petrece mai mult timp cu temele decât cu proiectul său pasional, un program de calculator care să învețe structura narativă a basmelor și să genereze altele noi.

„M-am gândit: „Uau, trebuie să iau asta în serios”,” și-a amintit Carmosino. În scurt timp, a fost atât de absorbit de subiect, încât mentorul său i-a sugerat cu blândețe să-și reconsidere planurile de după absolvire.

„El a spus: „Știi, dacă vrei să continui să faci asta, dacă vrei să continui să faci informatică teoretică și teoria complexității, poți: se numește școală de licență”, a spus Carmosino. După ce a obținut masterul, s-a mutat la San Diego în 2012 pentru a lucra la un doctorat coordonat de Impagliazzo.

Scopul principal al lui Carmosino, la început, a fost să înțeleagă mai bine a hârtie de reper de două decenii mai devreme care îi captivase imaginaţia. Lucrarea aceea, de către teoreticienii complexității Alexandru Razborov și Steven Rudich, a arătat că o anumită strategie „naturală” pentru a demonstra P ≠ NP va eșua aproape sigur, deoarece succesul ar avea un cost mare - distrugerea completă a criptografiei - pe care cercetătorii l-au considerat ca fiind foarte puțin probabil. Cercetătorii au interpretat rezultatul lui Razborov și Rudich ca o barieră în calea acestei abordări populare de a demonstra P ≠ NP.

Această „barieră a dovezilor naturale” este doar una dintre multele bariere cunoscute în rezolvarea problemelor deschise în teoria complexității. Fiecare acționează ca un obstacol, avertizând că o cale aparent promițătoare este de fapt o fundătură. Împreună, aceste bariere indică faptul că orice dovadă care rezolvă problema P versus NP ar trebui să fie radical diferită de orice folosit în trecut; de aceea majoritatea cercetătorilor cred că o soluție rămâne departe. Dar cel puțin barierele le spun unde să nu caute.

„Teoria complexității este atât blestemată, cât și binecuvântată cu atât de multe bariere”, a spus Ilango.

Când Carmosino a întâlnit bariera naturală a dovezilor, aceasta avea aproape 20 de ani. Dar bănuia că avea mai multe lecții pentru cercetători. Acest sentiment avea să fie justificat într-o zi când el și trei colegi au dovedit un rezultat surprinzător prin examinarea barierei dovezilor naturale din perspectiva meta-complexității. Dovada lor a fost unul dintre puținele rezultate majore care au stârnit un nou interes pentru meta-complexitate, ceea ce a condus la o rafală de progres în ultimii câțiva ani.

Dar pentru a urma traseul de la bariera dovezilor naturale până la meta-complexitate, va trebui să sărim înapoi la locul unde am lăsat cercetătorii în anii 1970, când au început să abordeze problema P versus NP. Ce a făcut să fie atât de greu să dovedești problemele?

O cale circuituală

La început, cercetătorii au încercat să demonstreze P ≠ NP - adică să demonstreze că unele probleme NP nu sunt rezolvabile prin niciun algoritm polinom posibil - folosind variații ale tehnicilor pe care le folosea Turing pentru a demonstra că unele probleme nu sunt rezolvabile cu niciun algoritm. . Dar ei repede a descoperit o dovadă că acele metode nu ar funcționa - prima barieră majoră în rezolvarea întrebării P versus NP. Așa că au început să caute o altă abordare și au găsit curând una în opera contemporanului lui Turing. claude shannon.

Shannon, care a crescut într-un orășel din nordul Michigan, părea o figură puțin probabilă să introducă era informației. Cu toate acestea, el a exemplificat natura interdisciplinară a disciplinei emergente a informaticii, simțindu-se la fel de bine în inginerie electrică și logica matematică. În a lui teza de masterat, Shannon a arătat cum circuitele realizate din comutatoare electromecanice ar putea reprezenta expresii logice care implică variabile booleene - cantități care pot lua doar două valori (cum ar fi adevărat sau fals, sau 1 și 0).

În aceste expresii, variabilele booleene sunt legate între ele prin „porțile logice” ȘI, SAU și NU. Expresia elementară A ŞI B, de exemplu, este adevărată atunci când atât A cât şi B sunt adevărate, iar false în caz contrar; A SAU B, pe de altă parte, este adevărată dacă cel puțin una dintre cele două variabile este adevărată. O poartă NOT este și mai simplă: inversează valoarea unei singure variabile. Cu suficiente din aceste blocuri de bază, puteți efectua orice calcul.

„Când te uiți la computerul tău, la sfârșitul zilei, ce face? Are un circuit”, a spus Ilango.

Lucrările lui Shannon au sugerat o nouă modalitate pentru teoreticieni de a gândi la dificultatea problemelor computaționale, numită „complexitate a circuitelor”, chiar dacă circuitele în cauză sunt doar abstractizări matematice. Pentru o vreme, cercetătorii au crezut că această abordare ar putea fi modalitatea de a rezolva P versus NP, dar în cele din urmă traseul s-a lovit de bariera dovezilor naturale.

Cadrul complexității circuitului necesită regândirea celor mai de bază concepte din modelul de calcul al lui Turing. Aici, în loc de probleme de calcul și algoritmi care le rezolvă, cercetătorii iau în considerare funcțiile booleene și circuitele care le calculează. O funcție booleană preia variabile booleene - adevărate și false, 1 și 0 - și scoate fie adevărat, fie fals, 1 sau 0. Și, ca un algoritm, un circuit descrie o procedură pentru producerea unei ieșiri având în vedere orice intrare.

„Înțeleg că oamenii au început să lucreze la complexitatea circuitelor pentru că au decis că mașinile Turing sunt prea complicate”, a spus Ryan Williams, un teoretician al complexității la MIT. „Putem studia circuitele poartă cu poartă.”

Așa cum pot exista mulți algoritmi pentru rezolvarea oricărei probleme de calcul date, unii mai rapid decât alții, multe circuite diferite pot calcula orice funcție booleană dată, unele cu porți mai puține decât altele. Cercetătorii definesc complexitatea circuitului unei funcții ca fiind numărul total de porți din cel mai mic circuit care o calculează. Pentru o funcție cu un număr fix de variabile de intrare, complexitatea circuitului este, de asemenea, un număr fix - mai mare pentru unele funcții decât pentru altele.

Dar, în multe cazuri, puteți lua în considerare versiuni mai complicate ale aceleiași funcții prin creșterea numărului de variabile de intrare, la fel cum puteți îngreuna problema drumului hamiltonian luând în considerare grafice mai mari. Apoi, cercetătorii iau în considerare aceeași întrebare pe care o pun atunci când studiază timpii de rulare a algoritmului: numărul minim de porți necesare pentru a calcula o funcție booleană crește polinomial sau exponențial pe măsură ce crește numărul de variabile de intrare? Cercetătorii numesc aceste două categorii de funcții „ușor de calculat” și, respectiv, „greu de calculat”.

O funcție booleană ușor de calculat este similară cu o problemă de calcul din clasa P - una care poate fi rezolvată printr-un algoritm care rulează în timp polinomial. Dar există și funcții analoge cu problemele NP dure, în care cel mai bun mod pe care cercetătorii au descoperit-o pentru a calcula versiuni progresiv mai mari necesită un număr în creștere exponențial de porți, dar răspunsul poate fi verificat cu ușurință. Dacă teoreticienii complexității ar putea demonstra că într-adevăr nu există o modalitate mai bună de a calcula o astfel de funcție, aceasta ar implica P ≠ NP.

Aceasta a fost strategia pe care au urmat-o majoritatea teoreticienilor în complexitate în anii 1980. Și șansele erau de partea lor. Shannon avea s-au dovedit în 1949, că aproape fiecare tabel de adevăr boolean (care este doar o listă lungă a tuturor intrărilor și ieșirilor posibile ale unei funcții booleene de dimensiune fixă) are o complexitate a circuitului care este practic cât mai mare posibil. El a folosit un argument uimitor de simplu: există mult mai puține moduri de a combina un număr mic de porți decât există modalități de a combina mai multe porți.

„Pur și simplu nu există suficiente circuite mici pentru a circula”, a spus Aaronson.

Deci, teoreticienii complexității s-au trezit într-o situație curioasă. Dacă aproape fiecare tabel de adevăr are o complexitate mare a circuitului, atunci aproape fiecare funcție booleană trebuie să fie greu de calculat. Cercetătorii au trebuit doar să identifice o singură astfel de funcție despre care se știa că face parte din clasa NP. Cât de greu poate fi?

Crypto Bros

La început, progresul a fost rapid. În 1981, Sipser și doi colaboratori s-au dovedit că o anumită funcție booleană era cu siguranță greu de calculat dacă foloseau circuite cu anumite restricții cu privire la modul în care ar putea fi aranjate porțile.

„Fantezia a fost că ai fi capabil să demonstrezi lucruri despre aceste modele restricționate și apoi să construiești pe ceea ce ai învățat să lucrezi cu tot mai puține restricții”, a spus Sipser.

În 1985, Razborov a făcut următorul pas mare. Tocmai începuse școala absolventă la Moscova și s-a alăturat efortului accidental în timp ce aborda o problemă dintr-o altă ramură a matematicii, unde s-a dovedit că rezolvarea problemei P versus NP era o condiție prealabilă.

„Am fost pur și simplu norocos că nu știam cât de dificilă este această problemă”, a spus Razborov. „Altfel, poate nici nu aș fi început.”

Razborov a analizat circuitele care conțin doar porți AND și SAU și s-au dovedit că o anumită funcție era greu de calculat folosind astfel de circuite, indiferent de modul în care erau aranjate porțile - mai mult, se știa că acea funcție este NP-completă. Tot ce au trebuit să facă cercetătorii pentru a rezolva P versus NP a fost să extindă tehnicile lui Razborov la circuite cu porți NU.

„A existat un fel de sentiment universal că încă un pas, încă o lovitură și vom obține”, a spus Razborov. Dar nu asta sa întâmplat. Razborov însuși a dovedit că metoda lui ar eșua dacă NU ar fi adăugate porți la amestec și nimeni nu ar putea găsi o altă cale de urmat. Pe măsură ce anii au trecut, el a început să se întrebe de ce urma s-a stins.

În Statele Unite, Rudich se gândea la aceeași întrebare. El și Impagliazzo erau colegi de facultate care absolviseră împreună școala. Prietenia lor fusese declanșată de o fascinație comună față de dovezile autoreferențiale ale lui Gödel și Turing și implicațiile lor pentru bazele matematicii și informaticii.

„Gluma noastră era că urma să obținem un buton care spunea „auto-referință”, a spus Impagliazzo.

În calitate de studenți absolvenți, atât Rudich, cât și Impagliazzo au lucrat la fundamentele teoretice ale complexității criptografiei, un subiect care oferă poate cea mai bună motivație practică pentru încercarea de a demonstra P ≠ NP. Criptografii ascunde mesajele secrete, învelindu-le în „pseudoradomness” - un mesaj criptat în acest fel va arăta ca un amestec aleatoriu de numere pentru orice interceptător, dar poate fi încă decodat de către destinatarul vizat. Dar cum poți fi sigur că unui posibil urmăritor va fi prea greu să încalce codul?

Aici intervine teoria complexității. Metodele de criptare cele mai utilizate astăzi sunt toate bazate pe probleme NP aparent grele - pentru a decripta mesajul, un atacator ar avea nevoie de un algoritm rapid, încă nedescoperit, pentru a rezolva problema. Pentru a stabili că aceste metode sunt cu adevărat sigure, un lucru pe care trebuie să-l faceți este să demonstrați că P ≠ NP. Fără o dovadă, a spus Sipser, tot ce poți face este „să speri că oricine de la care încerci să păstrezi secretul nu este un matematician mai bun decât tine”.

Deși fascinantă în sine, criptografia părea departe de argumentele autoreferențiale care îi atraseseră mai întâi pe Rudich și Impagliazzo în domeniu. Dar, pe măsură ce Rudich se străduia să înțeleagă de ce abordarea complexității circuitului stătuse, a început să realizeze că cele două subiecte nu erau atât de îndepărtate, până la urmă. Strategia pe care cercetătorii au adoptat-o ​​în încercările lor de a demonstra că P ≠ NP avea un caracter autoînfrâng care amintește de celebra propoziție a lui Gödel „această afirmație este de nedemonstrat” – iar criptografiile ar putea ajuta la explicarea de ce. În Rusia, Razborov a descoperit o legătură similară cam în același timp. Acestea au fost semințele barierei dovezilor naturale.

Tensiunea din centrul barierei dovezilor naturale este că sarcina de a distinge funcțiile cu complexitate ridicată de cele cu complexitate scăzută este similară cu sarcina de a distinge aleatorietatea adevărată de pseudoaleatoria folosită pentru a cripta mesajele. Am dori să arătăm că funcțiile de complexitate ridicată sunt categoric diferite de funcțiile de complexitate scăzută, pentru a demonstra P ≠ NP. Dar ne-am dori, de asemenea, ca pseudoaleatoria să fie imposibil de distins de aleatorie, să avem încredere în securitatea criptografiei. Poate că nu o putem avea în ambele sensuri.

O glumă crudă

În 1994, Razborov și Rudich și-au dat seama că au ajuns la perspective similare și au început să lucreze împreună pentru a-și combina rezultatele. Ei au observat mai întâi că toate încercările anterioare de a demonstra P ≠ NP folosind complexitatea circuitului au adoptat aceeași strategie generală: identificați o proprietate specială a unei funcții booleene NP-complete, apoi demonstrați că nicio funcție ușor de calculat nu ar putea împărtăși această proprietate. Aceasta ar arăta că funcția NP-completă aleasă a fost cu adevărat greu de calculat, dovedind P ≠ NP.

Sipser, Razborov și alții au folosit aceeași strategie cu succes pentru a-și demonstra rezultatele mai limitate și, în fiecare caz, proprietatea specială pe care cercetătorii au identificat-o era împărtășită de majoritatea funcțiilor booleene. Razborov și Rudich au inventat termenul „dovadă naturală” pentru a se referi la acest caz în care proprietatea a fost partajată pe scară largă, pur și simplu pentru că nu exista o alternativă cunoscută. Dacă dovezile „nenaturale” ar fi posibile, ar trebui să fie foarte contraintuitive și să merite numele.

Razborov și Rudich și-au dovedit apoi principalul rezultat: o dovadă naturală a P ≠ NP ar necesita o înțelegere foarte cuprinzătoare a modului în care funcțiile ușor de calculat și greu de calculat diferă și că cunoștințele ar putea alimenta, de asemenea, un algoritm rapid pentru identificarea ușoară. - pentru a calcula funcții chiar dacă sunt superficial complicate. Dacă teoreticienii complexității ar fi reușit să obțină o demonstrație naturală a lui P ≠ NP, ei ar fi descoperit o modalitate aproape infailibilă de a arunca o privire asupra unui tabel de adevăr arbitrar și de a determina dacă funcția corespunzătoare avea complexitate mare sau scăzută a circuitului - un rezultat mult mai puternic și mai general decât îşi propuseseră să demonstreze.

„Aproape că nu poți să nu obții mai mult decât ți-ai târziat”, a spus Carmosino.

Este ca și cum ai încerca să verifici o anumită declarație, dar fiecare încercare s-a transformat într-un plan pentru un detector de minciuni de uz general - ar părea prea frumos pentru a fi adevărat. Pentru teoreticienii complexității, puterea surprinzătoare a dovezilor naturale a făcut, de asemenea, succesul să pară mai puțin probabil. Dar dacă o astfel de dovadă ar fi reușit, consecințele neașteptate ar fi o veste proastă pentru criptografie, din cauza conexiunii dintre complexitatea circuitului și pseudoaleatorie.

Pentru a înțelege această conexiune, imaginați-vă că vă uitați la coloana de ieșire din tabelul de adevăr al unei funcții booleene cu multe variabile de intrare și înlocuiți fiecare „adevărat” cu 1 și fiecare „fals” cu 0:

Dacă funcția booleană are o complexitate ridicată a circuitului, acea listă lungă de ieșiri va fi, în principiu, imposibil de distins de un șir cu adevărat aleatoriu de 0 și 1 - unul obținut prin aruncarea în mod repetat a unei monede, să zicem. Dar dacă funcția are o complexitate redusă a circuitului, șirul trebuie să aibă o descriere simplă, succintă, chiar dacă pare complicată. Acest lucru îl face foarte asemănător cu șirurile pseudoaleatoare folosite în criptografie, a căror descriere succintă este mesajul secret îngropat în acea aparentă aleatorie.

Deci, rezultatul lui Razborov și Rudich a arătat că orice demonstrație naturală a P ≠ NP ar produce, de asemenea, un algoritm rapid care ar putea distinge șirurile pseudoaleatoare care conțin mesaje ascunse de cele cu adevărat aleatoare. Criptografia sigură ar fi imposibilă - exact opusul a ceea ce cercetătorii sperau să stabilească prin demonstrarea P ≠ NP.

Pe de altă parte, dacă criptografia sigură este posibilă, atunci dovezile naturale nu sunt o strategie viabilă pentru a demonstra P ≠ NP - o condiție prealabilă pentru criptografia sigură. Pe scurt, aceasta este bariera dovezilor naturale. Părea ca și cum teoreticienii complexității ar fi primit o glumă crudă.

„Dacă crezi în duritate, atunci ar trebui să crezi că este greu să dovedești duritatea”, a spus Kabanets.

În metavers

Acea conexiune dintre implicațiile conjecturii P ≠ NP și dificultatea de a dovedi a fost intrigantă, dar dificil de stabilit. În primul rând, bariera dovezilor naturale a blocat doar o abordare pentru a demonstra P ≠ NP. Pe de altă parte, a legat dificultatea de a demonstra P ≠ NP nu de P ≠ NP în sine, ci de existența criptografiei securizate - o problemă strâns legată, dar nu chiar echivalentă. Pentru a înțelege cu adevărat legătura, cercetătorii ar trebui să se familiarizeze cu meta-complexitatea.

„Există această intuiție că „oh, pentru că P ≠ NP, este dificil de demonstrat că P ≠ NP”, a spus Williams. „Dar pentru a înțelege chiar și această intuiție, trebuie să începeți să vă gândiți la sarcina de a demonstra ceva de genul P ≠ NP ca o problemă de calcul.”

Asta a făcut Kabanets ca student absolvent. A crescut în Ucraina și și-a terminat studiile de licență în informatică la doi ani după căderea Uniunii Sovietice. În frământările care au urmat, a avut puține ocazii să urmărească subiectele teoretice care îl interesau cel mai mult.

„Am vrut să fac ceva mai academic”, și-a amintit Kabanets. „Și am fost, de asemenea, curios să văd lumea.” S-a mutat în Canada pentru studii superioare și acolo a aflat despre bariera dovezilor naturale. Ca și Carmosino, Kabanets a fost încântat de rezultat. „Părea foarte profund că ai această legătură”, a spus el.

În 2000, spre sfârșitul perioadei sale de licență, a descoperit că bariera dovezilor naturale continuă să apară în conversațiile sale cu Jin-Yi Cai, un teoretician al complexității care vizita Toronto în perioada sabatică. Ei au început să vadă bariera nu ca pe un obstacol, ci ca pe o invitație – o oportunitate de a investiga cât de greu a fost să dovedesc problemele. The hârtie în care au expus această nouă perspectivă avea să devină una dintre cele mai influente lucrări timpurii în domeniul în curs de dezvoltare al meta-complexității.

Lucrarea lui Kabanets și Cai a evidențiat o problemă de calcul implicită în formularea lui Razborov și Rudich a barierei dovezilor naturale: Dată tabelul de adevăr al unei funcții booleene, determinați dacă are complexitate mare sau scăzută a circuitului. Au numit-o problema cu dimensiunea minimă a circuitului sau MCSP.

MCSP este o problemă de meta-complexitate prin excelență: o problemă de calcul al cărei subiect nu este teoria grafurilor sau un alt subiect extern, ci teoria complexității în sine. Într-adevăr, este ca o versiune cantitativă a întrebării care i-a determinat pe teoreticienii complexității să abordeze P versus NP folosind abordarea complexității circuitului în anii 1980: care funcții booleene sunt greu de calculat și care sunt ușor?

„Dacă am venit cu un algoritm MCSP, acesta ar fi ca o modalitate de a automatiza ceea ce facem în teoria complexității”, a spus Impagliazzo. „Ar trebui să ne ofere cel puțin o perspectivă extraordinară despre cum să ne facem treaba mai bine.”

Teoreticienii complexității nu își fac griji că acest algoritm magic îi scoate din funcțiune - ei nu cred că există deloc, deoarece Razborov și Rudich au arătat că orice astfel de algoritm pentru a distinge tabelele de adevăr cu complexitate ridicată de cele cu complexitate scăzută ar face criptografia. imposibil. Asta înseamnă că MCSP este probabil o problemă de calcul dificilă. Dar cât de greu este? Este NP-complet, la fel ca problema drumului hamiltonian și aproape orice altă problemă cu care s-au luptat cercetătorii în anii 1960?

Pentru probleme în NP, „cât de greu este?” este de obicei destul de ușor de răspuns, dar MCSP părea a fi o situație ciudată. „Avem foarte puține probleme „plutitoare” care nu au fost conectate la această insulă de probleme NP-complete, deși par a fi dificile”, a spus Kabanets.

Kabanets știa că el și Cai nu erau primii care au luat în considerare problema pe care o numeau MCSP. Matematicienii sovietici au studiat o problemă foarte asemănătoare începând cu anii 1950, într-o încercare timpurie de a înțelege dificultatea intrinsecă a diferitelor probleme de calcul. Leonid Levin s-a luptat cu ea în timp ce dezvolta ceea ce avea să devină teoria completității NP la sfârșitul anilor 1960, dar nu a putut dovedi că este NP-complet și și-a publicat lucrarea fundamentală fără ea.

După aceea, problema a atras puțină atenție timp de 30 de ani, până când Kabanets și Cai au remarcat legătura sa cu bariera dovezilor naturale. Kabanets nu se aștepta să rezolve el însuși întrebarea – în schimb a vrut să exploreze de ce a fost atât de greu să demonstreze că această problemă aparent grea despre duritatea computațională era de fapt grea.

„Este, într-un fel, meta-meta-complexitate”, a spus Rahul Santhanam, un teoretician al complexității la Universitatea din Oxford.

Dar a fost duritatea până la capăt sau a existat măcar o modalitate de a înțelege de ce cercetătorii nu au reușit să demonstreze că MCSP era NP-complet? Kabanets a descoperit că, da, a existat un motiv: dificultatea de a înțelege complexitatea circuitului acționează ca o barieră în calea oricărei strategii cunoscute pentru a demonstra completitatea NP a MCSP - o problemă care este în sine despre dificultatea înțelegerii complexității circuitului. Logica răsucită, autoînfrângătoare, a barierei dovezilor naturale părea de nescăpat.

De asemenea, este posibil ca MCSP să nu fie NP-complet, dar și asta pare puțin probabil - anumite variante mai simple ale problemei sunt deja cunoscute ca fiind NP-complete.

„Nu avem un loc frumos în care să-l punem în legătură directă cu toate celelalte probleme pe care le studiem”, a spus Impagliazzo.

Kabanets luminase comportamentul ciudat al MCSP, dar el nu știa cum să facă progrese suplimentare. Cercetarea meta-complexității a încetinit până la un filtru. Va înflori din nou 16 ani mai târziu, când cercetătorii au descoperit o legătură surprinzătoare cu o altă întrebare fundamentală: cât de greu este să rezolvi problemele dacă îți pasă doar să obții răspunsul corect de cele mai multe ori?

War of the Worlds

Pentru problemele de zi cu zi, răspunsurile care funcționează de cele mai multe ori sunt destul de bune. Ne planificăm naveta pentru modelele tipice de trafic, de exemplu, nu pentru scenariile cele mai defavorabile.

Cei mai mulți teoreticieni ai complexității sunt mai greu de satisfăcut: se mulțumesc să declare o problemă ușor doar dacă pot găsi un algoritm rapid care să obțină răspunsul corect la fiecare intrare posibilă. Această abordare standard clasifică problemele în funcție de ceea ce cercetătorii numesc complexitatea „cel mai rău caz”. Dar există și o teorie a complexității „cazului mediu”, în care problemele sunt considerate ușoare dacă există un algoritm rapid care obține răspunsul corect la majoritatea intrărilor.

Distincția contează pentru criptografi. Imaginați-vă o problemă de calcul care este ușor de rezolvat pentru aproape fiecare intrare, cu excepția câtorva cazuri încăpățânate în care cel mai bun algoritm eșuează. Teoria complexității în cel mai rău caz consideră că o problemă grea, dar pentru criptografie este inutilă: dacă doar unele dintre mesajele tale sunt greu de descifrat, ce rost are?

De fapt, Levin a fost cel care a inițiat studiul riguros al complexității medii a cazului, la un deceniu după munca sa de pionierat privind completitudinea NP. În anii care au urmat, el se înfruntase cu autoritățile sovietice - era un făcător de probleme ireverenți care submina uneori activitățile patriotice din grupul său de tineret al Partidului Comunist. În 1972, i s-a refuzat doctoratul din motive explicit politice.

„Pentru a avea succes în Uniunea Sovietică, ca tânăr cercetător, nu ai putea fi foarte obișnuit și este greu să-ți imaginezi că Leonid nu este obișnuit”, a spus Impagliazzo.

Levin a emigrat în Statele Unite în 1978, iar la mijlocul anilor 1980 și-a îndreptat atenția către complexitatea medie a cazurilor. El a început să lucreze cu alții pentru a dezvolta în continuare teoria, inclusiv Impagliazzo, un student absolvent la acea vreme. Dar chiar și pe măsură ce au făcut progrese, Impagliazzo a descoperit că cercetătorii au vorbit adesea între ei. El a vrut să-i pună pe toți pe aceeași pagină și nu a ajutat faptul că lucrările lui Levin erau renumite succinte - cea care a inițiat domeniul de complexitate medie a cazurilor a fost mai mică de două pagini.

„Voiam să fac o traducere a lucrării lui Leonid în termeni tehnici mai accesibili”, a spus Impagliazzo. El a decis să înceapă cu o prezentare scurtă și jucăușă a imaginii de ansamblu înainte de a se scufunda în matematică. „Acel fel a preluat ziarul și oricum e singura parte pe care cineva și-o amintește.”

hârtie, publicat în 1995, a devenit un clasic instant. Impagliazzo a inventat nume capricioase pentru cinci lumi se disting prin grade diferite de duritate computațională și capacități criptografice diferite. Trăim într-una dintre aceste lumi, dar nu știm care.

De când a apărut lucrarea lui Impagliazzo, cercetătorii au visat să elimine părți din multiversul său miniatural - îngustând spațiul posibilităților, demonstrând că unele dintre lumi nu sunt până la urmă posibile. Două lumi sunt ținte deosebit de tentante: cele în care criptografia este imposibilă chiar dacă P ≠ NP.

Într-una dintre aceste lumi, numită Heuristica, toate problemele NP-complete sunt ușor de rezolvat pe majoritatea intrărilor, dar algoritmii rapizi fac ocazional greșeli, așa că aceste probleme sunt încă considerate grele de standardele teoriei complexității cazului cel mai rău. Aceasta este lumea în care criptografia este imposibilă, deoarece aproape fiecare cod este ușor de spart. În cealaltă lume, numită Pessiland, criptografia este imposibilă dintr-un motiv diferit: fiecare problemă este grea în sensul de caz mediu, dar criptarea unui mesaj îl face ilizibil chiar și pentru destinatarul vizat.

Aceste două lumi se dovedesc a fi strâns legate de problemele de meta-complexitate - în special, soarta Heuristica este legată de întrebarea de lungă durată dacă MCSP este NP-complet. Întrebarea care l-a fascinat pe Kabanets și l-a zăpăcit pe Levin cu atâta timp în urmă nu este o simplă curiozitate: este o lume întreagă în joc.

Pentru a exclude Heuristica, cercetătorii ar trebui să restrângă distincția dintre complexitatea cazului cel mai rău și complexitatea cazului mediu - adică ar trebui să demonstreze că orice algoritm ipotetic care rezolvă corect o problemă NP-completă pe majoritatea intrărilor o poate rezolva de fapt. în toate cazurile. Se știe că acest tip de conexiune, numită reducere de la cel mai rău caz la caz mediu, există pentru anumite probleme, dar niciuna dintre ele nu este NP-completă, așa că acele rezultate nu implică nimic mai general. Eliminarea Heuristica ar duce criptografii la jumătatea drumului până la realizarea visului de criptare sigură bazată pe presupunerea unică că P ≠ NP.

Dar distrugerea unei lumi nu este o faptă mică. În 2003, doi teoreticieni ai complexității a arătat că abordările existente pentru a demonstra reducerile de la cel mai rău caz la mediu pentru problemele NP-complete cunoscute ar implica consecințe ciudate, sugerând că astfel de dovezi probabil nu sunt posibile.

Cercetătorii ar trebui să găsească o altă abordare și acum cred că MCSP ar putea fi tocmai problema de care au nevoie. Dar asta nu avea să devină clar timp de peste un deceniu. Prima privire a conexiunii a apărut din fascinația persistentă a lui Marco Carmosino față de bariera dovezilor naturale.

Carmosino a întâlnit pentru prima dată cercetarea meta-complexității ca student absolvent prin a Hârtie 2013 de Kabanets și alți patru cercetători, care au dezvoltat în continuare abordarea barierei dovezilor naturale pe care Kabanets o făcuse pionier cu mai mult de un deceniu mai devreme. Acest lucru nu a făcut decât să-i întărească convingerea că mai sunt încă de învățat din lucrarea clasică a lui Razborov și Rudich.

„Eram obsedat de acea ziare în acel moment”, a spus Carmosino. "Nimic nu a fost schimbat."

Obsesia a dat roade în cele din urmă în timpul unei vizite la un atelier de lucru semestrial la Universitatea din California, Berkeley, unde și-a petrecut cea mai mare parte a timpului vorbind cu Impagliazzo, Kabanets și Antonina Kolokolova, un teoretician al complexității la Universitatea Memorial din Newfoundland, care a colaborat cu Kabanets la lucrarea din 2013. Carmosino mai lucrase cu ei trei o dată, iar acea colaborare reușită i-a dat încrederea de a-i împroșca cu întrebări despre subiectul care l-a fascinat cel mai mult.

„El a deranjat oamenii într-un mod bun”, și-a amintit Kabanets.

La început, Carmosino a avut idei noi pentru a demonstra completitatea NP pentru versiunea MCSP care a apărut în lucrarea lui Razborov și Rudich despre bariera dovezilor naturale. Dar acele idei nu au rezultat. În schimb, o remarcă a lui Impagliazzo i-a făcut pe cei patru cercetători să realizeze că bariera dovezilor naturale ar putea produce algoritmi mai puternici decât și-ar fi dat seama oricine - a existat o hartă secretă gravată în barajul rutier.

Într-o Hârtie 2016, cei patru cercetători au dovedit că un anumit tip de algoritm MCSP pentru cazuri medii ar putea fi folosit pentru a construi un algoritm în cel mai rău caz pentru identificarea tiparelor ascunse în șiruri de cifre aleatoare - o sarcină la care oamenii de știință o numesc „învățare”. Este un rezultat izbitor, deoarece învățarea intuitiv pare mai grea decât sarcina de clasificare binară - complexitate mare sau complexitate scăzută - efectuată de un algoritm MCSP. Și, în mod surprinzător, a legat complexitatea cazului cel mai rău a unei sarcini de complexitatea cazului mediu a celeilalte.

„Nu era deloc evident că o astfel de conexiune ar exista deloc”, a spus Impagliazzo.

Un algoritm rapid pentru MCSP este pur ipotetic pentru circuitele booleene generale: nu poate exista decât dacă MCSP se dovedește a fi o problemă de calcul ușoară, în ciuda tuturor dovezilor contrare, și asta înseamnă că algoritmul de învățare implicat de lucrarea celor patru cercetători este la fel de ipotetică.

Dar pentru unele versiuni mai simple ale MCSP - care fac distincția dintre tabelele de adevăr cu complexitate ridicată de cele cu complexitate scăzută atunci când există restricții specifice asupra circuitelor - algoritmii rapidi sunt cunoscuți de mulți ani. Lucrarea lui Carmosino, Impagliazzo, Kabanets și Kolokolova a arătat că acești algoritmi ar putea fi transformați în algoritmi de învățare care erau la fel restricționați, dar totuși mai puternici decât oricare pe care cercetătorii l-au înțeles anterior la un nivel teoretic atât de riguros.

„Într-un fel, aroma lor auto-referențială vă permite să faceți lucruri pe care aparent nu le puteți face cu probleme mai standard”, a spus Ilango.

Rezultatul a atras atenția teoreticienilor complexității care lucrează pe alte subiecte. A fost, de asemenea, o previzualizare a conexiunilor ulterioare dintre meta-complexitatea și complexitatea medie a cazului care vor apărea în următorii ani.

Mai presus de toate, a fost o dovadă a cât de departe pot ajunge cercetătorii punând întrebări simple despre bariere care la început par doar să le împiedice progresul.

„Acest tip de dualitate este o temă în cel puțin ultimii 30 sau 40 de ani de complexitate”, a spus Impagliazzo. „Obstacolele sunt adesea oportunități.”

Credit parțial

Progresul s-a accelerat doar în anii de când Carmosino și colegii săi și-au publicat lucrarea.

„Se întâmplă lucruri noi”, a spus Kolokolova. „Există o mulțime de cercetători juniori cu adevărat, foarte străluciți.”

Ilango este unul dintre acești tineri cercetători – în primii trei ani de studii superioare, el a atacat problema descurajantă deschisă de a dovedi MCSP NP-complet folosind o strategie în două direcții: dovedirea NP-completate pentru simplu Versiunile a MCSP, așa cum au făcut cercetătorii privind complexitatea circuitelor când au atacat P versus NP în anii 1980, dovedind totodată completitudinea NP pentru versiuni mai complicate, care intuitiv par mai grele și, prin urmare, sunt poate mai ușor de dovedit greu.

Ilango își atribuie interesul pentru meta-complexitate Eric Allender, un teoretician al complexității la Universitatea Rutgers și unul dintre puținii cercetători care au continuat să lucreze la meta-complexitate în anii 2000 și începutul anilor 2010. „Entuziasmul lui a fost molipsitor”, a spus Ilango.

Un alt tânăr cercetător inspirat de Allender este Shuichi Hirahara, acum profesor la Institutul Național de Informatică din Tokyo. În timp ce era încă student absolvent în 2018, Hirahara a dezvăluit adevărata amploare a relației dintre meta-complexitatea și complexitatea medie a cazului pe care Carmosino și coautorii săi au descoperit-o. Acei patru cercetători au găsit o legătură între complexitatea medie a unei probleme – MCSP – și complexitatea celui mai rău caz a alteia – învățarea booleană. Hirahara și-a dezvoltat tehnicile în continuare deriva o reducere de la cel mai rău caz la mediu pentru MCSP. Rezultatul său implică faptul că un algoritm ipotetic MCSP pentru cazuri medii precum cel pe care Carmosino și colegii săi l-au considerat ar fi de fapt suficient de puternic pentru a rezolva o versiune ușor diferită a MCSP fără a face greșeli.

Rezultatul lui Hirahara este interesant, deoarece mulți cercetători bănuiesc că MCSP este NP-complet, spre deosebire de toate celelalte probleme pentru care se cunosc reduceri de la cel mai rău caz la mediu. Dacă ei pot extinde rezultatele lui Hirahara pentru a acoperi toți algoritmii de caz mediu și apoi pot demonstra că MCSP este NP-complet, asta ar dovedi că nu trăim în Heuristica.

„Acesta ar fi cu adevărat un rezultat cutremurător”, a spus Santhanam.

Demonstrarea că MCSP este NP-complet poate părea o problemă grea - la urma urmei, întrebarea este deschisă de peste 50 de ani. Dar după o descoperire anul trecut de către Hirahara, cercetătorii sunt acum mult mai apropiați decât s-ar fi așteptat oricine în urmă cu câțiva ani.

Hirahara a dovedit completitudinea NP pentru o variantă a problemei numită MCSP parțial, în care ignorați anumite intrări din fiecare tabel de adevăr. Dovada sa s-a bazat pe metode dezvoltate de Ilango pentru a arăta că MCSP parțial a fost echivalent cu o problemă aparent fără legătură care implică o tehnică criptografică numită partajare secretă. Aceasta este o modalitate de a împărți un mesaj criptat între multe persoane, astfel încât să poată fi decodificat numai dacă o anumită fracțiune dintre ei lucrează împreună.

Pentru orice aplicație reală în criptografie, ați dori să știți acea fracțiune în avans, dar cu ajutorul unor trucuri criptografice suplimentare, puteți construi un scenariu frustrant în care este greu să vă dați seama de câți oameni trebuie să coopereze. Hirahara a găsit o modalitate de a demonstra că această problemă criptografică artificială a fost NP-completă și apoi a arătat că dovada implica și NP-completitudinea MCSP parțial.

Acest rezultat a energizat cercetătorii în meta-complexitate chiar mai mult decât munca anterioară a lui Hirahara, iar alți cercetători au remarcat, de asemenea, – teoreticianul și bloggerul complexității Lance Fortnow l-a numit rezultatul anului. Acest lucru se datorează faptului că abordarea unor astfel de versiuni cu „funcție parțială” a problemelor de calcul a fost un pas intermediar cheie în alte dovezi de completitudine NP.

„Este o muncă uimitoare”, a spus Williams. „Toată lumea credea că aceste probleme parțiale erau aproximativ aceeași dificultate ca problema completă.”

Rămân impedimente pentru a demonstra completitatea NP pentru versiunea completă a MCSP. Dar niciuna nu este tipul de bariere care sugerează că este nevoie de un set de instrumente complet nou - poate fi doar o chestiune de găsire a modului potrivit de a combina tehnicile cunoscute. O dovadă ar stabili în cele din urmă statutul uneia dintre puținele probleme care au rezistat clasificării atâta timp cât a existat teoria complexității. Pe e-mail, Levin a scris: „M-ar umili să arăt că sunt prost pentru că nu am putut să-l văd :-).”

Piesele lipsă

MCSP nu este nici măcar singura problemă de meta-complexitate care a generat o descoperire majoră. În 2020, criptograful Cornell Tech Pasul Rafael și studentul său absolvent Yanyi Liu a descoperit o conexiune între o altă problemă de meta-complexitate și un protocol criptografic fundamental care definește granița dintre Heuristica și Pessiland, cea mai rea dintre lumi lui Impagliazzo (unde problemele NP-complete sunt grele în sensul mediu al cazului, dar criptografia este încă imposibilă). Asta face ca problema pe care au studiat-o să fie un candidat principal pentru un asalt asupra Pessiland și a lor lucrare mai recentă indică faptul că ar putea funcționa și împotriva lui Heuristica.

„Diferitele piese ale puzzle-ului lipsesc”, a spus Pass. „Pentru mine este pur și simplu magic că aceste câmpuri sunt atât de strâns legate.”

Hirahara avertizează că provocări încă îi așteaptă pe cercetătorii intenționați să distrugă lumile pe care Impagliazzo a evocat acum 30 de ani. „Aș dori să spun că la un moment dat Heuristica și Pessiland vor fi excluse, dar nu sunt sigur cât de aproape suntem”, a spus el.

Mulți cercetători se așteaptă ca cea mai mare dificultate să fie depășirea unui decalaj aparent inofensiv între două modele diferite de complexitate medie a cazurilor. Criptografii studiază de obicei algoritmii cu cazuri medii care greșesc în ambele direcții, ocazional etichetând greșit șirurile aleatoare drept pseudoaleatoare și invers. Între timp, reducerile de la cel mai rău caz la caz mediu ale lui Hirahara funcționează pentru algoritmi de caz mediu care fac doar primul tip de eroare. Distincții subtile ca aceasta pot face o lume de diferență în teoria complexității. Dar, în ciuda acestui obstacol și a multor altele, Allender nu se poate abține să nu sune o notă de optimism păzit.

„Încerc să nu mă las prea credincios pentru că există un istoric destul de bine stabilit de nimic care nu funcționează”, a spus el. „Dar vedem o mulțime de evoluții cu adevărat interesante – modalități de a depăși lucruri care păreau a bariere.”

Dacă există o lecție pe care cercetătorii au învățat-o din luptele lor de a răspunde la întrebarea P versus NP - sau chiar să o înțeleagă - este aceea că teoria complexității este ea însăși complexă. Dar această provocare este tocmai ceea ce face căutarea atât de plină de satisfacții.

„Este de fapt grozav că este atât de greu”, a spus Carmosino. „Nu mă voi plictisi niciodată.”

Nota editorului: Scott Aaronson este membru al Revista Quanta'S Consiliu consultativ.