Keerukuse teooria 50-aastane teekond teadmiste piiridesse | Ajakiri Quanta

2007. aasta sügissemestri esimesel nädalal tõmbas Marco Carmosino end matemaatikatundi, mis on vajalik kõigi arvutiteaduse erialade jaoks Massachusettsi ülikoolis Amherstis. Teisel kursusel õppiv Carmosino kaalus kolledžist väljalangemist, et videomänge kujundada. Seejärel esitas professor lihtsa küsimuse, mis muudaks tema elukäiku: kuidas sa tead, et matemaatika tegelikult töötab?

"See pani mind istuma ja tähelepanu pöörama," meenutas Carmosino, nüüd IBMi teoreetiline arvutiteadlane. Ta registreerus vabatahtlikule seminarile Kurt Gödeli loomingu kohta, kelle peadpööritavad eneseviiteargumendid paljastasid esmalt matemaatilise arutluskäigu piirid ja lõid aluse kogu edaspidiseks tööks arvutamise põhipiirangute alal. Seda oli palju sisse võtta.

"Ma ei saanud 100% aru," ütles Carmosino. "Aga ma teadsin, et tahan."

Tänapäeval leiavad isegi kogenud teadlased mõistmist, kui nad seisavad silmitsi teoreetilise arvutiteaduse keskse avatud küsimusega, mida tuntakse P versus NP probleemina. Sisuliselt küsib see küsimus, kas paljusid arvutusprobleeme, mida on pikka aega peetud äärmiselt raskeks, saab tegelikult lihtsalt lahendada (salajase otsetee kaudu, mida me pole veel avastanud) või, nagu enamik teadlasi kahtlustab, on need tõesti rasked. Kaalul ei ole midagi vähemat kui teadaoleva olemus.

Hoolimata teadlaste aastakümnetepikkustest jõupingutustest arvutusliku keerukuse teooria valdkonnas - selliste küsimuste uurimine erinevate probleemide sisemise raskuse kohta - on P versus NP küsimuse lahendamine jäänud tabamatuks. Ja pole isegi selge, kust peaks algama võimalik tõestus.

"Teekaarti pole," ütles Michael Sipser, Massachusettsi Tehnoloogiainstituudi veteran keerukuse teoreetik, kes 1980ndatel aastaid probleemiga maadeldes. "See on nagu sa läheksid kõrbe."

Näib, et arvutusprobleemide raske lahendamise tõestamine on iseenesest raske ülesanne. Aga miks see nii raske on? Ja kui raske see on? Carmosino ja teised metakeerukuse alavaldkonna uurijad sõnastavad sellised küsimused ümber arvutusprobleemidena, tõukuvad valdkonda edasi, pöörates keerukuseteooria objektiivi enda peale tagasi.

"Võite mõelda:" OK, see on lahe. Võib-olla on keerukuse teoreetikud hulluks läinud, ”ütles Rahul Ilango, MIT-i magistrant, kes on andnud selles valdkonnas viimase aja põnevamaid tulemusi.

Neid sissepoole suunatud küsimusi uurides on teadlased õppinud, et arvutusliku kõvaduse tõestamise raskus on tihedalt seotud põhiküsimustega, mis võivad alguses tunduda mitteseotud. Kui raske on ilmselt juhuslikes andmetes peidetud mustreid märgata? Ja kui tõesti rasked probleemid on olemas, siis kui sageli need rasked on?

"On saanud selgeks, et metakeerukus on asjade keskmes," ütles Scott Aaronson, keerukuse teoreetik Texase ülikoolis Austinis.

See on lugu pikast ja käänulisest rajast, mis viis teadlased P versus NP probleemi juurest metakeerukuseni. See ei ole olnud kerge teekond – rada on täis valesid pöördeid ja teetõkkeid ning see loob end ikka ja jälle tagasi. Kuid metakeerukuse uurijatele on see teekond kaardistamata maastikule omaette tasu. Hakka esitama näiliselt lihtsaid küsimusi, ütles Valentine Kabanets, Kanada Simon Fraseri ülikooli keerukuse teoreetik ja "teil pole õrna aimugi, kuhu lähete."

Teadaolevad tundmatud

P versus NP probleem võlgneb oma nõrga nime keerukuse teoreetikute harjumusele sortida arvutusprobleeme laiadeks.keerukusklassid” Nasdaqi märgisümbolitele viitavate siltidega. Arvutusülesanne on selline, mida saab põhimõtteliselt lahendada algoritmiga – täpselt määratletud juhiste loendiga. Kuid mitte kõik algoritmid pole võrdselt kasulikud ja algoritmide erinevus viitab põhimõttelistele erinevustele erinevate klasside probleemide vahel. Keerukuse teoreetikute väljakutse on muuta need vihjed rangeteks teoreemideks keerukusklasside vaheliste suhete kohta.

Need seosed peegeldavad muutumatuid tõdesid arvutamise kohta, mis ulatuvad palju kaugemale mis tahes konkreetsest tehnoloogiast. "See on nagu universumi seaduste avastamine," ütles Kabanets.

"P" ja "NP" on a kaks kõige kuulsamat liiget kasvav loomakoda sadadest keerukusklassidest. Jämedalt öeldes on P probleemide klass, mida saab hõlpsasti lahendada, näiteks loendi tähestiku järgi koostamine. NP on probleemide klass, millel on kergesti kontrollitavad lahendused, näiteks sudokud. Kuna kõiki kergesti lahendatavaid ülesandeid on ka lihtne kontrollida, on P ülesanded ka NP-s. Kuid mõned NP-probleemid tunduvad olevat raskesti lahendatavad – te ei saa sudoku-mõistatuse lahendust kohe intuiteerida, proovimata esmalt paljusid võimalusi. Kas võib olla, et see näiline kõvadus on lihtsalt illusioon – et iga kergesti kontrollitava probleemi lahendamiseks on üks lihtne nipp?

Kui jah, siis P = NP: kaks klassi on samaväärsed. Kui see nii on, peab olema mingi algoritm, mis muudab tohutute sudokude lahendamise, ülemaailmsete laevateede optimeerimise, moodsa krüptimise katkestamise ja matemaatiliste teoreemide tõestuste automatiseerimise triviaalseks. Kui P ≠ NP, siis jäävad paljud põhimõtteliselt lahendatavad arvutusülesanded praktikas igaveseks meie haardeulatusest välja.

Teadlased tundsid muret formaalse matemaatilise arutluskäigu piiride pärast ammu enne probleemi P versus NP esimest sõnastamist – tõepoolest ammu enne kaasaegse arvutiteaduse algust. Aastal 1921, maadeldes sama küsimusega, mis võitis Carmosino tähelepanu peaaegu sajand hiljem, pakkus matemaatik David Hilbert välja uurimisprogrammi matemaatika täielikuks maandamiseks. Ta lootis lähtuda mõnest lihtsast eeldusest, mida nimetatakse aksioomideks, ja tuletada ühtse matemaatilise teooria, mis vastas kolmele põhikriteeriumile.

Hilberti esimene tingimus, järjepidevus, oli põhinõue, et matemaatika oleks vastuoludeta: kui saaks tõestada kahte vastuolulist väidet, lähtudes samadest aksioomidest, oleks kogu teooria päästmatu. Kuid teooria võiks olla vastuoludeta ja selle ulatus siiski piiratud. See oli Hilberti teise tingimuse, täielikkuse, ajendiks: nõue, et kõik matemaatilised väited oleksid kas tõestatavalt tõesed või tõestatavalt valed. Tema kolmas kriteerium, otsustatavus, nõudis üheselt mõistetavat mehaanilist protseduuri, et teha kindlaks, kas mõni matemaatiline väide on tõene või väär. Hilbert kuulutas 1930. aastal konverentsil kõneledes: „Meie loosung on „Me peame teadma, me saame teada”.

Vaid aasta hiljem andis Gödel Hilberti unenäole esimese hoobi. Tema tõestatud et sellise ennasthävitava väite nagu “see väide on tõestamatu” võib tuletada mis tahes sobivast aksioomide komplektist. Kui selline väide on tõepoolest tõestamatu, on teooria poolik, kuid kui see on tõestatav, on teooria vastuoluline - veelgi hullem tulemus. Samas töös tõestas Gödel ka, et ükski matemaatiline teooria ei suuda kunagi tõestada oma järjepidevust.

Teadlased avaldasid endiselt lootust, et tulevane matemaatikateooria, kuigi see on tingimata puudulik, võib siiski osutuda otsustavaks. Võib-olla võiksid nad välja töötada protseduurid, mis tuvastaksid kõik tõestatavad väited, hoidudes samal ajal eemale tüütutest ettepanekutest, nagu Gödeli oma. Probleem oli selles, et keegi ei teadnud, kuidas neid hüpoteetilisi protseduure põhjendada.

Seejärel sõnastas 1936. aastal 23-aastane magistrant nimega Alan Turing ümber Hilberti otsustatavuse tingimuse tol ajal võõras arvutuskeeles ja andis sellele surmava hoobi. Turing sõnastas matemaatilise mudeli - nüüd tuntud kui Turingi masin — mis võiks esindada kõiki võimalikke algoritme ja näitas, et kui Hilberti protseduur oleks olemas, sobiks see sellesse mudelisse. Seejärel kasutas ta enesele viitavaid meetodeid nagu Gödel tõestama otsustamatute väidete olemasolu või samaväärselt arvutamatud probleemid, mida ükski algoritm ei suudaks lahendada.

Hilberti programm oli varemetes: tõestatavale ja arvutatavale on igavesti põhimõttelised piirangud. Kuid kui arvutid arenesid teoreetilistest abstraktsioonidest reaalsete masinateni, mõistsid teadlased, et Turingi lihtne eristamine lahendatavate ja lahendamatute probleemide vahel jättis paljud küsimused vastuseta.

1960. aastateks olid arvutiteadlased mõne probleemi lahendamiseks välja töötanud kiired algoritmid, samas kui teiste jaoks olid ainsad teadaolevad algoritmid piinavalt aeglased. Mis siis, kui küsimus poleks ainult selles, kas probleemid on lahendatavad, vaid kui raske on neid lahendada?

"Tekib rikkalik teooria ja me ei tea enam vastuseid," ütles Carmosino.

Erinevad teed

Et illustreerida, kui segadust tekitavad küsimused kõvaduse kohta võivad olla, vaatleme paari tihedalt seotud probleemi, mis hõlmavad graafikuid. Need on punktide võrgud, mida nimetatakse sõlmedeks ja mida ühendavad jooned, mida nimetatakse servadeks. Arvutiteadlased kasutavad neid kõike modelleerimiseks kvantarvutus Euroopa liiklusvoog.

Oletame, et teile antakse graafik ja palutakse leida midagi, mida nimetatakse Hamiltoni teeks – marsruut, mis läbib iga sõlme täpselt ühe korra. See probleem on põhimõtteliselt selgelt lahendatav: võimalikke teid on ainult piiratud arv, nii et kui kõik muu ebaõnnestub, võite lihtsalt kontrollida iga. See on hea, kui sõlmpunkte on vähe, kuid isegi veidi suuremate graafikute puhul väljub võimaluste arv kontrolli alt, muutes selle lihtsa algoritmi kiiresti kasutuks.

On keerukamaid Hamiltoni tee algoritme, mis suudavad paremini võidelda, kuid algoritmidel kuluv aeg probleemi lahendamiseks kasvab alati plahvatuslikult koos graafiku suurusega. Graafikud ei pea olema väga suured, enne kui isegi parimad algoritmide uurijad on avastanud, et nad ei leia teed "mingi mõistliku aja jooksul", ütles Russell Impagliazzo, San Diego California ülikooli keerukuse teoreetik. "Ja "mõistliku aja" all pean silmas "enne universumi lõppu".

Hamiltoni tee probleemil on veel üks huvitav omadus. Kui keegi väidab, et on leidnud konkreetselt graafikult Hamiltoni tee, saate kiiresti kontrollida, kas lahendus on kehtiv, isegi kui graafik on väga suur. Kõik, mida pead tegema, on järgida teed ja märgistada sõlmed ükshaaval, kontrollides, kas te pole ühtegi sõlme kaks korda märkinud. Kui lõpus pole ühtegi sõlme puudu, on tee Hamiltoni.

Selle lahenduse kontrollimise algoritmi käitamiseks kuluv aeg on võrdeline graafiku suurusega. See asetab selle polünoomalgoritmide laiemasse kategooriasse, mille tööajad pikenevad graafiku suuruse polünoomfunktsioonidega. Polünoomikasv on eksponentsiaalse kasvuga võrreldes taltsas, seega jäävad polünoomialgoritmid elujõuliseks ka suurtel graafikutel. "See on oluliselt tõhusam, " ütles Carmosino.

Hamiltoni teeprobleemil on selle suhtes terav asümmeetria: õiget lahendust saate kontrollida kiire polünoomialgoritmi abil, kuid lahenduse leidmiseks vajate aeglast eksponentsiaalset algoritmi. See asümmeetria ei pruugi tunduda üllatav – kunstilist meistriteost on lihtsam ära tunda kui seda luua, lihtsam on kontrollida matemaatilist tõestust kui tõestada uut teoreemi – ometi ei ole kõigil arvutusprobleemidel seda asümmeetrilist iseloomu. Tegelikult käitub Hamiltoni radade leidmisega väga sarnane probleem hoopis teisiti.

Oletame, et teile antakse jälle graaf, kuid nüüd palutakse teil leida "Euleri tee", mis ületab iga serva täpselt ühe korra. Jällegi on võimalike lahenduste kontrollimiseks olemas polünoomalgoritm, kuid seekord on ülesande lahendamiseks ka polünoomalgoritm. Siin pole asümmeetriat. Keerukuse teoorias tundub, et mõnda teed on lihtsam leida kui teisi.

Nii Hamiltoni tee probleem kui ka Euleri tee probleem on keerukusklassis NP, mis on määratletud nii, et see hõlmab kõiki probleeme, mille lahendusi saab kontrollida polünoomalgoritmidega. Euleri teeprobleem kuulub samuti klassi P, kuna polünoomalgoritm suudab selle lahendada, kuid Hamiltoni teeprobleemi puhul see ei kehti. Miks peaksid need kaks pealiskaudselt nii sarnast graafikuülesannet nii dramaatiliselt erinema? See on P versus NP probleemi olemus.

Universaalselt raske

Alguses tundusid keerukusklassid mugavad kategooriad sarnaste, kuid otseselt mitte seotud probleemide sortimiseks – keegi ei kahtlustanud, et Hamiltoni radade leidmisel on midagi pistmist muude raskete arvutusprobleemidega.

1971. aastal, aasta jooksul pärast Toronto ülikooli ümberasumist pärast seda, kui temalt keelduti ametist USA-s, oli keerukuse teoreetik. Stephen Cook avaldatud erakordne tulemus. Ta tuvastas konkreetse NP-probleemi kummalise tunnusega: kui on olemas polünoomalgoritm, mis suudab selle probleemi lahendada, saab see lahendada ka kõik teised NP-s olevad probleemid. Cooki "universaalne" probleem näis olevat üksildane veerg, mis toetas näiliselt raskete probleemide klassi, eraldades need allpool toodud lihtsatest probleemidest. Lahendage see üks probleem ja ülejäänud NP kukub kokku.

Cook kahtlustas, et tema universaalse probleemi jaoks pole kiiret algoritmi, ja ütles sama palju paberi keskel, lisades: "Ma arvan, et selle oletuse tõestamiseks tasub kulutada märkimisväärseid jõupingutusi." "Märkimisväärne pingutus" osutuks alahinnatuks.

Umbes samal ajal nimetas Nõukogude Liidus aspirant Leonid Levin tõestas a sarnane tulemus, välja arvatud see, et ta tuvastas mitu erinevat universaalset probleemi. Lisaks Ameerika kompleksiteoreetik Richard Karp tõestatud et Cooki (ja Levini, kuigi Karp ja Cook teadsid Levini tööst alles aastaid hiljem) tuvastatud universaalsuse omadus oli ise kõike muud kui universaalne. Peaaegu igal NP-probleemil, millel polnud teadaolevat polünoomialgoritmi – st peaaegu igal kergesti kontrollitaval probleemil, mis tundus raske – oli sama omadus, mida hakati nimetama NP-täielikkuseks.

See tähendab kõiki NP-ga seotud probleeme – Hamiltoni tee probleemi, sudokut ja tuhandeid teistest — on täpses mõttes samaväärsed. "Teil on kõik need erinevad loomulikud ülesanded ja need kõik osutuvad võluväel samadeks ülesandeks," ütles Ilango. "Ja me ei tea ikka veel, kas sama ülesanne on võimalik või mitte."

P versus NP küsimuse lahendamiseks piisaks mis tahes NP-täieliku probleemi raskuste lahendamisest. Kui P ≠ NP, eristavad lihtsaid ja raskeid probleeme tuhanded veerud, mis on kõik võrdselt tugevad. Kui P = NP, kõigub kogu ehitis kokkuvarisemise äärel, oodates, kuni mõni tükk maha kukub.

Cook, Levin ja Karp olid ühendanud palju seosetuid probleeme. Nüüd pidid keerukuse teoreetikud lahendama vaid ühe probleemi: kas P = NP või mitte?

Viiskümmend aastat hiljem jääb see küsimus vastuseta. Kabanets võrdles arvutamise piiride üle arutlemist tohutu territooriumi mõõdistamisega, ilma et oleks mingit tervikpilti. Piiramatu arvutusvõimsusega olend võiks mäetipust alla vaadata ja kogu maastikku korraga haarata, kuid lihtsurelikud ei saa sellisele eelisele loota. "Need, kes me mäe põhjas viibime, võivad parema vaate saamiseks proovida võib-olla üles-alla hüpata," ütles ta.

Oletame, et P = NP. Selle tõestamiseks peaksid teadlased leidma kiire algoritmi NP-täieliku probleemi jaoks, mis võib peituda selle tohutu maastiku mõnes ebaselges nurgas. Pole mingit garantiid, et nad selle niipea üles leiavad: keerukuse teoreetikud on seda aeg-ajalt teinud avastasin geniaalsed algoritmid näiliselt raskete (kuigi mitte NP-täielike) probleemide lahendamiseks alles pärast aastakümnete pikkust tööd.

Oletame nüüd, et P ≠ NP. Selle tõestamine tundub veelgi raskem. Keerukuse teoreetikud peaksid kindlaks tegema, et kiiret algoritmi ei saa eksisteerida, ennetades ja nurjades tõhusalt kõigi tulevaste teadlaste parimad jõupingutused.

Probleemi osaks on teadmatus, kust alustada. Kuid see pole nii, nagu teadlased poleks proovinud. Aastakümnete jooksul on nad probleemi rünnanud mitme nurga alt ja leidnud, et tee on igal sammul blokeeritud. "See on üks räigemaid tõdesid teoreetilises arvutiteaduses," ütles Carmosino. "Kui teil on nähtus, mis on nii vastupidav, tahate selgitust."

Carmosino viimaseks kolledžiaastaks oli tema uudishimu viinud ta Gödelist keerukuseteooria kraadiõppesse. Ta oli üllatunud, kui mõistis, et kulutab rohkem aega kodutöödele kui oma kireprojektile – arvutiprogrammile, mis õpiks muinasjuttude narratiivse ülesehituse ja genereeriks uusi.

"Mõtlesin: "Vau, ma pean seda tõsiselt võtma," meenutas Carmosino. Varsti oli ta sellest teemast nii süvenenud, et mentor soovitas tal õrnalt oma lõpetamisjärgsed plaanid uuesti läbi vaadata.

"Ta ütles:" Teate, kui soovite seda jätkata, kui soovite jätkata teoreetilise arvutiteaduse ja keerukuse teooriaga tegelemist, saate: seda nimetatakse kõrgkooliks," ütles Carmosino. Pärast magistrikraadi omandamist kolis ta 2012. aastal San Diegosse, et töötada doktorikraadi nimel, mida juhendas Impagliazzo.

Carmosino peamine eesmärk oli alguses paremini mõista a maamärk paber kaks aastakümmet varasemast, mis oli tema kujutlusvõimet haaranud. See paber keerukuse teoreetikute poolt Aleksander Razborov ja Steven Rudich, oli näidanud, et teatud "loomulik" strateegia P ≠ NP tõestamiseks kukub peaaegu kindlasti läbi, sest edu kaasneks järsu hinnaga – krüptograafia täielik lagunemine –, mida teadlased pidasid väga ebatõenäoliseks. Teadlased tõlgendasid Razborovi ja Rudichi tulemust tõkkena sellele populaarsele lähenemisele P ≠ NP tõestamisel.

See "loodusliku tõestuse barjäär" on vaid üks paljudest teadaolevatest takistustest keerukusteooria avatud probleemide lahendamisel. Igaüks neist toimib teetõkkena, hoiatades, et näiliselt paljutõotav tee on tegelikult ummiktee. Üheskoos näitavad need tõkked, et kõik tõendid, mis lahendavad P versus NP probleemi, peaksid olema radikaalselt erinevad kui kõik, mida varem kasutati; Seetõttu usub enamik teadlasi, et lahendus jääb kaugele. Kuid vähemalt tõkked ütlevad neile, kust mitte vaadata.

"Keerukuse teooria on nii neetud kui ka õnnistatud paljude takistustega," ütles Ilango.

Selleks ajaks, kui Carmosino puutus kokku loodusliku tõestustõkkega, oli see peaaegu 20 aastat vana. Kuid ta kahtlustas, et sellel on teadlastele rohkem õppetunde. See tunne saab ühel päeval õigustatud, kui ta ja kolm kolleegi osutusid üllatavaks tulemuseks, uurides loomulike tõendite barjääri metakeerukuse vaatenurgast. Nende tõestus oli üks vähestest peamistest tulemustest, mis tekitas uue huvi metakeerukuse vastu, mis viis viimaste aastate jooksul tohutu eduni.

Kuid selleks, et jälgida rada loomuliku tõestuse barjäärist meta-keerukuseni, peame hüppama tagasi sinna, kuhu me jätsime teadlased 1970. aastatel, kui nad hakkasid esimest korda tegelema P versus NP probleemiga. Mis tegi probleemide raskeks tõestamise nii keeruliseks?

Ringitav tee

Alguses püüdsid teadlased tõestada, et P ≠ NP – st tõestada, et mõned NP probleemid ei ole lahendatavad ühegi võimaliku polünoomalgoritmiga – kasutades Turingi kasutatud tehnikate variatsioone tõestamaks, et mõningaid probleeme ei saa lahendada ühegi algoritmiga. . Aga nad kiiresti avastasin tõend selle kohta, et need meetodid ei tööta – esimene suurem takistus P versus NP küsimuse lahendamisel. Nii hakkasid nad otsima teist lähenemist ja peagi leidsid nad selle Turingi kaasaegsete töödes claude shannon.

Shannon, kes kasvas üles Põhja-Michigani väikelinnas, tundus ebatõenäoline tegelane teabeajastu sissejuhatamiseks. Ometi näitas ta tärkava arvutiteaduse distsipliini interdistsiplinaarset olemust, tundes end võrdselt koduselt nii elektrotehnikas kui ka matemaatilises loogikas. Tema omas magistritöö, Shannon näitas, kuidas elektromehaanilistest lülititest valmistatud ahelad võivad kujutada loogilisi avaldisi, mis hõlmavad Boole'i ​​muutujaid - suurusi, mis võivad omandada ainult kaks väärtust (nt tõene või väär või 1 ja 0).

Nendes avaldistes seovad Boole'i ​​muutujad omavahel "loogikaväravad" JA, VÕI ja EI. Näiteks elementaaravaldis A JA B on tõene, kui nii A kui ka B on tõesed, ja muul juhul väär; A VÕI B seevastu on tõene, kui vähemalt üks kahest muutujast on tõene. NOT värav on veelgi lihtsam: see inverteerib ühe muutuja väärtuse. Kui neid põhilisi ehitusplokke on piisavalt, saate teha mis tahes arvutusi.

"Kui vaatate oma arvutisse päeva lõpuks, mida see teeb? See jookseb ringrajal,” ütles Ilango.

Shannoni töö pakkus teoreetikutele välja uue viisi, kuidas mõelda arvutusprobleemide keerukusele, mida nimetatakse "vooluahela keerukusele", kuigi kõnealused ahelad on lihtsalt matemaatilised abstraktsioonid. Mõnda aega arvasid teadlased, et see lähenemine võiks olla viis P versus NP lahendamiseks, kuid lõpuks jooksis jälg vastu loomuliku tõestusbarjääri.

Ahela keerukuse raamistik nõuab Turingi arvutusmudeli kõige põhilisemate kontseptsioonide ümbermõtestamist. Siin arvestavad teadlased arvutusprobleemide ja neid lahendavate algoritmide asemel Boole'i ​​funktsioone ja neid arvutavaid ahelaid. Boole'i ​​funktsioon võtab sisse Boole'i ​​muutujad – tõesed ja valed, 1-d ja 0-d – ning väljastab tõese või väära, 1 või 0. Ja nagu algoritm, kirjeldab ahel protseduuri väljundi loomiseks mis tahes sisendi korral.

"Ma saan aru, et inimesed hakkasid vooluahela keerukuse kallal töötama, kuna nad otsustasid, et Turingi masinad on liiga keerulised," ütles Ryan Williams, MIT-i keerukuse teoreetik. "Saame uurida vooluringe värav värava haaval."

Nii nagu mis tahes arvutusprobleemi lahendamiseks võib olla palju algoritme, millest mõned on kiiremad kui teised, saavad paljud erinevad ahelad arvutada mis tahes Boole'i ​​funktsiooni, mõnedel on vähem väravaid kui teistel. Teadlased määratlevad funktsiooni ahela keerukuse kui väravate koguarvu väikseimas vooluringis, mis seda arvutab. Fikseeritud arvu sisendmuutujatega funktsiooni puhul on ahela keerukus ka fikseeritud arv — mõne funktsiooni puhul suurem kui teiste puhul.

Kuid paljudel juhtudel võite kaaluda sama funktsiooni keerukamaid versioone, suurendades sisendmuutujate arvu, nii nagu saate Hamiltoni tee probleemi raskendada, kui arvestada suuremaid graafikuid. Seejärel kaaluvad teadlased sama küsimust, mida nad küsivad algoritmi tööaegu uurides: kas Boole'i ​​funktsiooni arvutamiseks vajalik minimaalne väravate arv kasvab sisendmuutujate arvu suurenedes polünoomiliselt või eksponentsiaalselt? Teadlased nimetavad neid kahte funktsioonide kategooriat vastavalt "kergesti arvutatavaks" ja "raskesti arvutatavaks".

Kergesti arvutatav Boole'i ​​funktsioon sarnaneb arvutusprobleemiga klassis P – see, mida saab lahendada polünoomilises ajas töötava algoritmiga. Kuid on ka funktsioone, mis on analoogsed raskete NP-probleemidega, kus parim viis, mille teadlased on avastanud järk-järgult suuremate versioonide arvutamiseks, nõuab eksponentsiaalselt kasvavat väravate arvu, kuid vastust saab hõlpsasti kontrollida. Kui keerukuse teoreetikud suudaksid tõestada, et sellise funktsiooni arvutamiseks pole paremat viisi, tähendaks see P ≠ NP.

See oli strateegia, mida enamik keerukuse teoreetikuid 1980. aastatel järgis. Ja tõenäosus oli nende poolel. Shannonil oli tõestatud aastal 1949, et peaaegu igal Boole'i ​​tõetabelil (mis on vaid pikk nimekiri fikseeritud suurusega Boole'i ​​funktsiooni kõigist võimalikest sisenditest ja väljunditest) on vooluahela keerukus, mis on praktiliselt võimalikult kõrge. Ta kasutas hämmastavalt lihtsat argumenti: väikese arvu väravate kombineerimiseks on palju vähem võimalusi kui paljude väravate kombineerimiseks.

"Seal pole lihtsalt piisavalt väikeseid ringradasid, et ringi liikuda," ütles Aaronson.

Nii leidsid keerukuse teoreetikud end kurioosses olukorras. Kui peaaegu igal tõetabelil on kõrge vooluahela keerukus, siis peaaegu iga Boole'i ​​funktsiooni peab olema raske arvutada. Teadlased pidid lihtsalt tuvastama ühe sellise funktsiooni, mis teadaolevalt kuulus ka klassi NP. Kui raske see olla võiks?

Crypto Bros

Alguses oli areng kiire. 1981. aastal Sipser ja kaks kaastöötajat tõestatud et teatud Boole'i ​​funktsiooni oli kindlasti raske arvutada, kui nad kasutasid ahelaid, millel on teatud piirangud väravate paigutusele.

"Fantasia seisnes selles, et saate tõestada asju nende piiratud mudelite kohta ja seejärel toetuda sellele, mida olete õppinud, et töötada üha vähemate piirangutega, " ütles Sipser.

1985. aastal astus Razborov järgmise suure sammu. Ta oli just alustanud Moskvas aspirantuuri ja ühines sellega kogemata, kui ta tegeles probleemiga teises matemaatika harus, kus selgus, et P versus NP probleemi lahendamine oli eeltingimus.

"Mul lihtsalt vedas, et ma ei teadnud, kui raske see probleem on," ütles Razborov. "Muidu poleks ma võib-olla isegi alustanud."

Razborov analüüsis ahelaid, mis sisaldavad ainult JA ja VÕI väravaid, ja tõestatud et konkreetset funktsiooni oli selliste ahelate abil raske arvutada, olenemata väravate paigutusest – veelgi enam, see funktsioon oli teadaolevalt NP-täielik. Kõik, mida teadlased pidid P versus NP lahendamiseks tegema, oli Razborovi tehnikate laiendamine NOT-väravatega ahelatele.

"Tekkis mingi universaalne tunne, et üks samm, veel üks löök ja me saame selle," ütles Razborov. Aga nii see ei juhtunud. Razborov ise tõestas, et tema meetod ebaõnnestub, kui segule EI lisata väravaid ja keegi ei leia teist teed edasi. Aastate möödudes hakkas ta mõtlema, miks see rada välja oli kadunud.

Ameerika Ühendriikides mõtiskles Rudich sama küsimuse üle. Tema ja Impagliazzo olid kolledži klassikaaslased, kes olid koos lõpetanud. Nende sõpruse põhjustas ühine vaimustus Gödeli ja Turingi enesele viitavatest tõestustest ning nende mõjust matemaatika ja arvutiteaduse alustele.

"Meie nali oli see, et kavatseme hankida nupu, millel oli kirjas "eneseviite"," ütles Impagliazzo.

Kraadiõppuritena töötasid nii Rudich kui ka Impagliazzo krüptograafia keerukusteoreetiliste aluste kallal – teemal, mis pakub võib-olla parimat praktilist motivatsiooni P ≠ NP tõestamiseks. Krüptograafid varjavad salasõnumeid, varjates neid "pseudojuhuslikkusega" – sel viisil krüpteeritud sõnum näeb iga pealtkuulaja jaoks välja nagu juhuslik numbrite segadus, kuid adressaat saab selle siiski dekodeerida. Kuid kuidas saate olla kindel, et potentsiaalsel pealtkuulajal on koodi murdmine liiga keeruline?

Siin tulebki mängu keerukuse teooria. Tänapäeval enim kasutatavad krüpteerimismeetodid põhinevad näiliselt rasketel NP-probleemidel – sõnumi dekrüpteerimiseks vajaks ründaja probleemi lahendamiseks veel avastamata kiiret algoritmi. Et teha kindlaks, kas need meetodid on tõeliselt turvalised, peate tõestama, et P ≠ NP. Sipser ütles, et ilma tõendita ei saa teha muud, kui "loota, et see, kelle eest sa üritad saladust hoida, pole parem matemaatik kui sina."

Kuigi krüptograafia oli omaette põnev, tundus see olevat kaugel enesele viitavatest argumentidest, mis olid esmalt Rudichi ja Impagliazzo valdkonda tõmbanud. Kuid kui Rudich püüdis aru saada, miks vooluringi keerukuse lähenemine takerdus, hakkas ta mõistma, et need kaks subjekti ei ole ometigi nii kaugel. Strateegiauurijad võtsid kasutusele oma katsed tõestada, et P ≠ NP oli ennasthävitav iseloom, mis meenutas Gödeli kuulsat väidet "see väide on tõestamatu" - ja krüptograafia võib aidata selgitada, miks. Venemaal avastas Razborov sarnase seose umbes samal ajal. Need olid loodusliku tõestusbarjääri seemned.

Loomuliku tõestuse barjääri keskmes on pinge, et kõrge keerukusega funktsioonide eristamine madala keerukusega funktsioonidest on sarnane ülesandega eristada tõelist juhuslikkust sõnumite krüpteerimiseks kasutatavast pseudojuhuslikkusest. Tahaksime näidata, et suure keerukusega funktsioonid on kategooriliselt erinevad madala keerukusega funktsioonidest, tõestamaks P ≠ NP. Kuid me sooviksime ka, et pseudojuhuslikkust ei saaks eristada juhuslikkusest, et olla kindlad krüptograafia turvalisuses. Võib-olla me ei saa seda mõlemat pidi.

Julm nali

1994. aastal mõistsid Razborov ja Rudich, et nad on tabanud sarnaseid arusaamu, ja hakkasid oma tulemuste ühendamiseks koostööd tegema. Esmalt täheldasid nad, et kõik varasemad katsed tõestada P ≠ NP ahela keerukuse abil olid võtnud kasutusele sama üldise strateegia: tuvastada NP-täieliku Boole'i ​​funktsiooni eriomadus, seejärel tõestada, et ükski lihtsalt arvutatav funktsioon ei saa seda omadust jagada. See näitaks, et valitud NP-täielikku funktsiooni oli tõesti raske arvutada, tõestades, et P ≠ NP.

Sipser, Razborov ja teised olid seda sama strateegiat edukalt kasutanud oma piiratumate tulemuste tõestamiseks ning igal juhul jagas teadlaste tuvastatud eriomadust enamik Boole'i ​​funktsioone. Razborov ja Rudich võtsid kasutusele termini "loomulik tõend", et viidata sellele juhtumile, kus vara jagati laialdaselt lihtsalt seetõttu, et teadaolevat alternatiivi ei olnud. Kui "ebaloomulikud" tõendid oleksid võimalikud, peaksid need olema väga intuitiivsed ja väärivad nime.

Seejärel tõestasid Razborov ja Rudich oma peamist tulemust: P ≠ NP loomulikuks tõestuseks oleks vaja väga põhjalikku arusaama sellest, kuidas hõlpsasti arvutatavad ja raskesti arvutatavad funktsioonid erinevad, ning need teadmised võiksid ka toita kiiret algoritmi lihtsaks tuvastamiseks. -funktsioonide arvutamiseks, isegi kui need on pealiskaudselt keerulised. Kui keerukuse teoreetikutel oleks õnnestunud P ≠ NP loomulik tõestus, oleksid nad avastanud peaaegu eksimatu viisi suvalise tõetabeli vaatamiseks ja kindlaks teha, kas vastava funktsiooni ahela keerukus on kõrge või madal – see on palju tugevam ja üldisem tulemus kui nad olid püüdnud tõestada.

"Sa ei saa peaaegu midagi muud, kui saate rohkem, kui olete kokku leppinud," ütles Carmosino.

Näib, nagu oleksite püüdnud konkreetset väidet faktiliselt kontrollida, kuid iga katse muutus üldotstarbelise valedetektori plaaniks – see tunduks liiga hea, et tõsi olla. Keerukuse teoreetikute jaoks muutis loomulike tõendite üllatav jõud ka edu vähem tõenäoliseks. Kuid kui selline tõestus oleks õnnestunud, oleksid ootamatud tagajärjed krüptograafia jaoks halvad uudised, kuna ahela keerukuse ja pseudojuhuslikkuse vahel on seos.

Selle seose mõistmiseks kujutage ette, et vaatate paljude sisendmuutujatega Boole'i ​​funktsiooni tõesuse tabelis väljundveergu ja asendate iga "tõene" 1-ga ja iga "väär" 0-ga:

Kui Boole'i ​​funktsioonil on suur vooluahela keerukus, ei saa seda pikka väljundite loendit põhimõtteliselt eristada tõeliselt juhuslikust 0-de ja 1-de jadast, mis saadakse näiteks mündi korduval viskamisel. Kuid kui funktsiooni ahela keerukus on madal, peab stringil olema lihtne ja lühike kirjeldus, isegi kui see tundub keeruline. See muudab selle väga sarnaseks krüptograafias kasutatavate pseudojuhuslike stringidega, mille kokkuvõtlik kirjeldus on salasõnum, mis on selle näilise juhuslikkuse alla maetud.

Seega näitas Razborovi ja Rudichi tulemus, et iga P ≠ NP loomulik tõestus annab ka kiire algoritmi, mis suudab eristada peidetud sõnumeid sisaldavad pseudojuhuslikud stringid tõeliselt juhuslikest. Turvaline krüptograafia oleks võimatu – täpselt vastupidine sellele, mida teadlased lootsid luua P ≠ NP tõestamisega.

Teisest küljest, kui turvaline krüptograafia on võimalik, ei ole loomulikud tõendid mõistlik strateegia P ≠ NP tõestamiseks – turvalise krüptograafia eelduseks. See on lühidalt loomulik tõestustõke. Näis, nagu oleksid keerukuse teoreetikud julma nalja vastu võtnud.

"Kui usute kõvadusse, siis peaksite uskuma, et kõvadust on raske tõestada," ütles Kabanets.

Metaversesse

See seos P ≠ NP oletuse tagajärgede ja selle tõestamise raskuse vahel oli intrigeeriv, kuid keeruline kindlaks teha. Esiteks blokeeris loomulike tõendite barjäär ainult ühe lähenemisviisi P ≠ NP tõestamiseks. Teiseks seostas see P ≠ NP tõestamise raskusi mitte P ≠ NP endaga, vaid turvalise krüptograafia olemasoluga - see on tihedalt seotud, kuid mitte päris samaväärne probleem. Seose tõeliseks mõistmiseks peaksid teadlased meta-keerukusega rahul olema.

"Seal on selline intuitsioon, et "oh, kuna P ≠ NP, on raske tõestada, et P ≠ NP"," ütles Williams. "Kuid selleks, et seda intuitsiooni isegi mõtestada, peate hakkama mõtlema ülesandele tõestada midagi sellist nagu P ≠ NP arvutusprobleemina."

Seda Kabanets aspirandina tegigi. Ta oli üles kasvanud Ukrainas ja lõpetas arvutiteaduse bakalaureuseõppe kaks aastat pärast Nõukogude Liidu lagunemist. Järgnenud segaduses oli tal vähe võimalusi tegeleda nende teoreetiliste teemadega, mis teda enim huvitasid.

"Tahtsin teha midagi akadeemilisemat," meenutas Kabanets. "Ja mul oli ka uudishimu maailma näha." Ta kolis Kanadasse kraadiõppesse ja seal õppis ta tundma loomulike tõendite barjääri. Nagu Carmosino, oli Kabanets tulemusest vaimustuses. "See tundus väga sügav, et teil on see side," ütles ta.

Aastal 2000, oma kooliaja lõpu poole, avastas ta, et loomuliku tõestuse barjäär kerkis pidevalt esile tema vestlustes Jin-Yi Cai, keerukuse teoreetik, kes viibis sel ajal Torontos hingamispuhkusel. Nad hakkasid tõket nägema mitte teetõkkena, vaid kutsena – võimalusena täpselt uurida, kui raske oli probleeme raskelt tõestada. The paber milles nad selle uue vaatenurga paika panid, muutuks üheks mõjukamaks varaseks teoseks tekkivas metakeerukuse valdkonnas.

Kabanetsi ja Cai artikkel tõi esile arvutusprobleemi, mis kaudselt sisaldub Razborovi ja Rudichi loomuliku tõestuse barjääri sõnastuses. Arvestades Boole'i ​​funktsiooni tõesuse tabelit, tehke kindlaks, kas sellel on kõrge või madal vooluahela keerukus. Nad nimetasid seda minimaalse vooluringi suuruse probleemiks või MCSP-ks.

MCSP on põhiline metakeerukuse probleem: arvutuslik probleem, mille teemaks ei ole graafiteooria või mõni muu väline teema, vaid keerukuse teooria ise. Tõepoolest, see on nagu kvantitatiivne versioon küsimusest, mis ajendas keerukuse teoreetikuid 1980. aastatel ahela keerukuse lähenemisviisi kasutades käsitlema P versus NP: milliseid Boole'i ​​funktsioone on raske arvutada ja milliseid on lihtne?

"Kui me leiaksime MCSP-algoritmi, oleks see nagu viis automatiseerida seda, mida me keerukuse teoorias teeme," ütles Impagliazzo. "See peaks vähemalt andma meile tohutu ülevaate sellest, kuidas oma tööd paremini teha."

Keerukuseteoreetikud ei muretse selle pärast, et see maagiline algoritm nad töölt ära paneb – nad ei usu, et see üldse olemas on, sest Razborov ja Rudich näitasid, et iga selline algoritm, mis võimaldab eristada kõrge keerukusega tõetabeleid madala keerukusega tabelitest, muudaks krüptograafia. võimatu. See tähendab, et MCSP on tõenäoliselt raske arvutuslik probleem. Aga kui raske see on? Kas see on NP-täielik, nagu Hamiltoni tee probleem ja peaaegu kõik teised probleemid, millega teadlased 1960. aastatel võitlesid?

NP probleemide korral "kui raske see on?" on tavaliselt piisavalt lihtne vastata, kuid MCSP tundus olevat kummaline kõrvalekalle. "Meil on väga vähe "ümber hõljuvaid" probleeme, mis pole olnud seotud selle NP-täielike probleemide saarega, kuigi need tunduvad olevat rasked," ütles Kabanets.

Kabanets teadis, et tema ja Cai polnud esimesed, kes kaalusid probleemi, mille nad olid nimetanud MCSP-ks. Nõukogude matemaatikud olid 1950. aastatest uurinud väga sarnast probleemi, püüdes varakult mõista erinevate arvutusprobleemide olemuslikku raskust. Leonid Levin oli sellega maadelnud, töötades välja teooriat, millest sai 1960. aastate lõpul NP-täielikkuse teooria, kuid ta ei suutnud tõestada, et see on NP-täielik, ja ta avaldas oma põhjapaneva artikli ilma selleta.

Pärast seda pälvis probleem 30 aastat vähe tähelepanu, kuni Kabanets ja Cai märkasid selle seost loomuliku tõestusbarjääriga. Kabanets ei lootnud selle küsimuse ise lahendada – selle asemel tahtis ta uurida, miks oli olnud nii raske tõestada, et see näiliselt raske arvutusliku kõvaduse probleem oli tegelikult raske.

"See on teatud mõttes meta-meta keerukus," ütles Rahul Santanam, keerukuse teoreetik Oxfordi ülikoolist.

Kuid kas see oli kõvadus või oli vähemalt kuidagi võimalik mõista, miks teadlastel ei õnnestunud tõestada, et MCSP oli NP-täielik? Kabanets avastas, et jah, sellel oli põhjus: ahela keerukuse mõistmise raskus toimib tõkkena mis tahes teadaolevale MCSP NP-täielikkuse tõestamise strateegiale - probleem, mis ise on seotud ahela keerukuse mõistmise raskusega. Loomuliku tõestuse barjääri keerutatud, ennasthävitav loogika tundus olevat möödapääsmatu.

Samuti on võimalik, et MCSP ei ole NP-täielik, kuid seegi tundub ebatõenäoline – probleemi teatud lihtsamad variandid on juba teadaolevalt NP-täielikud.

"Meil lihtsalt ei ole ilusat kohta, kus see oleks otseselt seotud kõigi teiste uuritavate probleemidega," ütles Impagliazzo.

Kabanets oli valgustanud MCSP kummalist käitumist, kuid ta ei teadnud, kuidas edasi liikuda. Meta keerukuse uurimine aeglustus. See õitses uuesti 16 aastat hiljem, kui teadlased avastasid üllatava seose teise põhiküsimusega: kui raske on probleeme lahendada, kui hoolite enamasti ainult õige vastuse saamisest?

Maailmade sõda

Igapäevaprobleemide puhul on sageli piisavad vastused, mis toimivad enamasti. Planeerime oma pendelrände näiteks tüüpiliste liiklusmustrite järgi, mitte halvima stsenaariumi järgi.

Enamikke keerukuse teoreetikuid on raskem rahuldada: nad on rahul probleemi lihtsaks tunnistamisega vaid siis, kui nad leiavad kiire algoritmi, mis saab igale võimalikule sisendile õige vastuse. See standardne lähenemine klassifitseerib probleemid vastavalt sellele, mida teadlased nimetavad "halvimaks juhuks". Kuid on olemas ka "keskmise juhtumi" keerukuse teooria, mille kohaselt probleeme peetakse lihtsaks, kui on olemas kiire algoritm, mis saab enamiku sisendite puhul õige vastuse.

Eristamine on krüptograafide jaoks oluline. Kujutage ette arvutusprobleemi, mida on lihtne lahendada peaaegu iga sisendi puhul, välja arvatud mõned kangekaelsed juhtumid, kus parim algoritm ebaõnnestub. Halvima keerukuse teooria peab seda raskeks probleemiks, kuid krüptograafia jaoks on see kasutu: kui ainult mõnda teie sõnumit on raske dešifreerida, siis mis mõte sellel on?

Tegelikult oli Levin see, kes algatas juhtumite keskmise keerukuse põhjaliku uurimise, kümme aastat pärast tema teedrajavat tööd NP-täielikkuse alal. Vahepealsetel aastatel oli ta sattunud vastuollu nõukogude võimudega – ta oli aupakmatu korrarikkuja, kes aeg-ajalt õõnestas isamaalist tegevust oma kommunistliku partei noorterühmas. 1972. aastal jäeti talle doktorikraad selgesõnalistel poliitilistel põhjustel ilma.

"Selleks, et noore teadlasena Nõukogude Liidus edukas olla, ei saa te olla väga oma arvamusega ja on raske ette kujutada, et Leonid ei oleks oma arvamusega," ütles Impagliazzo.

Levin emigreerus 1978. aastal USA-sse ja 1980. aastate keskel pööras ta tähelepanu keskmiste juhtumite keerukusele. Ta alustas teooria edasiarendamiseks koostööd teistega, sealhulgas Impagliazzoga, kes oli tol ajal magistrant. Kuid isegi edu saavutamisel avastas Impagliazzo, et teadlased rääkisid sageli üksteisest mööda. Ta tahtis kõik ühele lehele saada ja see ei aidanud, et Levini paberid olid kuulsalt napisõnalised – see, mis algatas valdkonna keskmise keerukusega juhtum oli alla kahe lehekülje pikk.

"Ma kavatsesin tõlkida Leonidi töö paremini kättesaadavatesse tehnilistesse terminitesse," ütles Impagliazzo. Enne matemaatikasse sukeldumist otsustas ta alustada lühikese mängulise ülevaatega üldpildist. "See võttis paberi üle ja see on ainus osa, mida keegi niikuinii mäletab."

. paber1995. aastal ilmunud, sai koheselt klassikaks. Impagliazzo lõi neile kapriissed nimed viis maailma mida eristab arvutuslik kõvadus ja erinevad krüptograafilised võimalused. Me elame ühes neist maailmadest, kuid me ei tea, millises.

Alates Impagliazzo artikli ilmumisest on teadlased unistanud tema miniatuurse multiversumi osade kõrvaldamisest – võimaluste ruumi kitsendamiseks, tõestades, et osa maailmadest pole siiski võimalikud. Kaks maailma on eriti ahvatlevad sihtmärgid: need, kus krüptograafia on võimatu, kuigi P ≠ NP.

Ühes neist maailmadest, mida nimetatakse Heuristicaks, on kõik NP-täielikud probleemid enamiku sisendite puhul hõlpsasti lahendatavad, kuid kiired algoritmid teevad aeg-ajalt vigu, mistõttu peetakse neid probleeme halvima juhtumi keerukuse teooria standardite kohaselt endiselt raskeks. See on maailm, kus krüptograafia on võimatu, sest peaaegu iga kood on kergesti murtud. Teises maailmas, mida nimetatakse Pessilandiks, on krüptograafia võimatu teisel põhjusel: iga probleem on keskmises tähenduses raske, kuid sõnumi krüpteerimine muudab selle loetamatuks isegi ettenähtud adressaadi jaoks.

Need kaks maailma osutuvad tihedalt seotud metakeerukuse probleemidega – eelkõige on Heuristica saatus seotud pikaajalise küsimusega, kas MCSP on NP-täielik. Küsimus, mis Kabanetsit nii kaua aega tagasi paelus ja Levinit jänni ajas, ei ole pelgalt uudishimu: kaalul on terve maailm.

Heuristica välistamiseks peaksid teadlased kaotama vahe halvima ja keskmise keerukuse vahel – see tähendab, et nad peavad tõestama, et iga hüpoteetiline algoritm, mis lahendab NP-täieliku probleemi enamiku sisendite puhul õigesti, suudab selle ka tegelikult lahendada. kõigil juhtudel. Selline ühendus, mida nimetatakse halvima juhtumi ja keskmise juhtude vähendamiseks, on teadaolevalt teatud probleemide korral olemas, kuid ükski neist pole NP-täielik, nii et need tulemused ei tähenda midagi üldisemat. Heuristica kõrvaldamine viiks krüptograafidel poolel teel unistuse elluviimisest turvalisest krüptimisest, mis põhineb ühel eeldusel, et P ≠ NP.

Kuid maailma hävitamine pole väike saavutus. 2003. aastal kaks keerukuse teoreetikut näitas et olemasolevad lähenemisviisid teadaolevate NP-täielike probleemide halvima ja keskmise vähenemise tõestamiseks tooksid kaasa äärmuslikud tagajärjed, mis viitab sellele, et sellised tõendid pole tõenäoliselt võimalikud.

Teadlased peaksid leidma teise lähenemisviisi ja nüüd arvavad nad, et MCSP võib olla just see probleem, mida nad vajavad. Kuid see ei saanud selgeks üle kümne aasta. Esimene pilguheit seosele tekkis Marco Carmosino pidevast vaimustuses loomuliku tõestusbarjääri vastu.

Carmosino puutus metakeerukuse uurimisega esimest korda kokku magistrandina läbi a 2013 paber Kabanetsi ja nelja teise teadlase poolt, kes arendasid edasi lähenemist loomulike tõendite barjäärile, mille Kabanets oli teerajajaks rohkem kui kümme aastat varem. See ainult tugevdas tema veendumust, et Razborovi ja Rudichi klassikalisest paberist on veel rohkem õppida.

"Olin tol ajal sellest paberist kinnisideeks," ütles Carmosino. "Midagi ei ole muutunud."

Kinnisidee kandis lõpuks vilja, kui ta külastas semestrit kestnud töötuba California ülikoolis Berkeleys, kus ta veetis suurema osa ajast vesteldes Impagliazzo, Kabanetsi ja Antonina Kolokolova, Newfoundlandi Memorialiülikooli keerukuse teoreetik, kes tegi Kabanetsiga koostööd 2013. aasta artiklis. Carmosino oli nende kolmega varem ühe korra koostööd teinud ja see edukas koostöö andis talle kindlustunde esitada neile küsimusi teemal, mis teda enim paelus.

"Ta segas inimesi heas mõttes," meenutas Kabanets.

Alguses olid Carmosinol uued ideed NP-täielikkuse tõestamiseks MCSP versiooni jaoks, mis oli ilmunud Razborovi ja Rudichi loomuliku tõestuse barjääri käsitlevas dokumendis. Kuid need ideed ei läinud täide. Selle asemel pani Impagliazzo märkus neljale teadlasele mõistma, et loomuliku tõestuse barjäär võib anda võimsamaid algoritme, kui keegi oli mõistnud – teetõkkesse oli söövitatud salajane kaart.

Aastal 2016 paber, tõestasid neli teadlast, et teatud tüüpi keskmise MCSP-algoritmi saab kasutada halvima algoritmi loomiseks juhusliku välimusega numbrijadadesse peidetud mustrite tuvastamiseks – see ülesanne, mida arvutiteadlased nimetavad „õppimiseks”. See on silmatorkav tulemus, sest intuitiivne õppimine tundub raskem kui MCSP-algoritmi abil teostatav binaarne klassifitseerimisülesanne – kõrge keerukus või madal keerukus. Ja üllataval kombel seostas see ühe ülesande halvima keerukuse teise ülesande keskmise keerukusega.

"Pole ilmne, et selline seos üldse eksisteeriks," ütles Impagliazzo.

MCSP kiire algoritm on üldiste Boole'i ​​ahelate jaoks puhtalt hüpoteetiline: see ei saa eksisteerida, kui MCSP ei osutu lihtsaks arvutusprobleemiks, hoolimata kõigist vastupidistest tõenditest, ja see tähendab, et nelja teadlase töös ette nähtud õppimisalgoritm on sama hüpoteetiline.

Kuid mõnede lihtsamate MCSP versioonide puhul – eristades suure keerukusega tõetabeleid madala keerukusega tabelitest, kui vooluringidele on kehtestatud spetsiifilised piirangud – on kiireid algoritme tuntud juba aastaid. Carmosino, Impagliazzo, Kabanetsi ja Kolokolova artikkel näitas, et neid algoritme saab muuta õppimisalgoritmideks, mis olid samuti piiratud, kuid siiski võimsamad kui kõik, mida teadlased olid varem nii rangel teoreetilisel tasemel mõistnud.

"Mingil moel võimaldab nende enesele viitav maitse teha asju, mida te näiliselt ei saa teha tavalisemate probleemidega," ütles Ilango.

Tulemus köitis teiste teemadega tegelevate keerukuseteoreetikute tähelepanu. See oli ka eelvaade edasistele seostele meta-keerukuse ja keskmise juhtumi keerukuse vahel, mis ilmnevad lähiaastatel.

Eelkõige oli see tunnistus sellest, kui kaugele võivad teadlased jõuda, esitades lihtsaid küsimusi tõkete kohta, mis esialgu näivad ainult takistavat nende arengut.

"Selline duaalsus on teemaks vähemalt viimase 30 või 40 keerukuse aasta jooksul," ütles Impagliazzo. "Takistused on sageli võimalused."

Osaline krediit

Edenemine on ainult kiirenenud aastate jooksul pärast Carmosino ja tema kolleegide avaldamist.

"Toimub uusi asju," ütles Kolokolova. "Seal on palju tõeliselt, tõeliselt säravaid nooremteadlasi."

Ilango on üks neist noortest teadlastest – oma esimesel kolmel kraadiõppeaastal ründas ta hirmuäratavat lahtist probleemi, milleks on MCSP NP täielikkuse tõestamine, kasutades kahesuunalist strateegiat: NP täielikkuse tõestamine lihtsam versioonid MCSP-st, nagu tegid ahela keerukuse uurijad, kui 1980. aastatel ründasid P versus NP, tõestades samal ajal ka NP-täielikkust keerulisemad versioonid, mis tunduvad intuitiivselt raskemad ja seega on neid võib-olla lihtsam tõestada.

Ilango tunnustab oma huvi metakeerukuse vastu Eric Allender, keerukuse teoreetik Rutgersi ülikoolist ja üks väheseid teadlasi, kes jätkas tööd metakeerukuse kallal 2000. aastatel ja 2010. aastate alguses. "Tema entusiasm oli nakkav," ütles Ilango.

Teine Allenderist inspireeritud noor teadlane on Shuichi Hirahara, nüüd Tokyo riikliku informaatikainstituudi professor. Olles 2018. aastal veel kraadiõppur, paljastas Hirahara metakeerukuse ja juhtumite keskmise keerukuse vahelise seose tõelise ulatuse, mille Carmosino ja tema kaasautorid olid avastanud. Need neli teadlast olid leidnud seose ühe probleemi – MCSP – keskmise keerukuse ja teise – Boole’i õppimise – halvima keerukuse vahel. Hirahara arendas oma tehnikaid edasi kõrvalekalle MCSP puhul halvima juhu keskmine vähendamine. Tema tulemus viitab sellele, et hüpoteetiline keskmise juhtumiga MCSP-algoritm, nagu Carmosino ja tema kolleegid arvasid, oleks tegelikult piisavalt võimas, et lahendada MCSP-st pisut erinev versioon ilma vigu tegemata.

Hirahara tulemus on põnev, sest paljud teadlased kahtlustavad, et MCSP on NP-täielik, erinevalt kõigist muudest probleemidest, mille puhul on teada halvima ja keskmise juhtumi vähenemine. Kui nad suudavad laiendada Hirahara tulemusi nii, et need hõlmaksid kõiki keskmiste juhtumite algoritme ja seejärel tõestaksid, et MCSP on NP-täielik, tõestaks see, et me ei ela Heuristicas.

"See oleks tõesti maad vapustav tulemus," ütles Santhanam.

Tõestada, et MCSP on NP-täielik, võib tunduda raske tellimus – lõppude lõpuks on küsimus olnud avatud üle 50 aasta. Kuid pärast a läbimurre eelmisel aastal Hirahara poolt on teadlased nüüd palju lähemal, kui keegi oleks paar aastat tagasi oodanud.

Hirahara tõestas NP-täielikkust probleemi variandi puhul, mida nimetatakse osaliseks MCSP-ks, mille puhul ignoreerite iga tõesuse tabeli teatud kirjeid. Tema tõend põhines Ilango välja töötatud meetoditel, et näidata, et osaline MCSP oli samaväärne näiliselt mitteseotud probleemiga, mis hõlmab krüptotehnikat, mida nimetatakse salajagamiseks. See on viis krüptitud sõnumi jagamiseks paljude inimeste vahel nii, et seda saab dekodeerida ainult siis, kui teatud osa neist töötab koos.

Mis tahes tegeliku krüptograafiarakenduse jaoks soovite seda murdosa ette teada, kuid täiendavate krüptograafiliste trikkide abil saate luua pettumust valmistava stsenaariumi, mille puhul on raske lihtsalt aru saada, kui palju inimesi koostööd tegema peavad. Hirahara leidis viisi, kuidas tõestada, et see väljamõeldud krüptograafiline probleem oli NP-täielik, ja näitas seejärel, et tõestus viitab ka osalise MCSP NP-täielikkusele.

See tulemus andis metakeerukuse uurijatele energiat isegi rohkem kui Hirahara varasem töö ning ka teised teadlased panid tähele – keerukuse teoreetik ja blogija Lance Fortnow nimetas seda aasta tulemus. Selle põhjuseks on asjaolu, et selliste arvutusprobleemide "osafunktsiooniga" versioonide käsitlemine on olnud oluline vaheetapp teistes NP-täielikkuse tõendites.

"See on hämmastav töö," ütles Williams. "Kõik arvasid, et need osalised probleemid on ligikaudu sama rasked kui kogu probleem."

MCSP täisversiooni NP-täielikkuse tõestamisel on endiselt takistusi. Kuid ükski ei ole selline takistus, mis viitaks täiesti uue tööriistakomplekti vajalikkusele – võib-olla tuleb lihtsalt leida õige viis tuntud tehnikate kombineerimiseks. Tõestus lahendaks lõpuks ühe vähestest probleemidest, mis on klassifitseerimisele vastu seisnud nii kaua, kui keerukuseteooria on eksisteerinud. Levin kirjutas meili teel: "See alandaks mind, kui näitaksin, et olen loll, kuna ma seda ei näinud :-)."

Kadunud tükid

MCSP pole isegi ainus metakeerukuse probleem, mis on ajendanud suurt läbimurret. 2020. aastal Cornell Techi krüptograaf Rafaeli pass ja tema magistrant Yanyi Liu avastas seose erineva metakeerukuse probleemi ja fundamentaalse krüptograafilise protokolli vahel, mis määrab piiri Heuristica ja Pessilandi vahel, Impagliazzo maailma halvima maailma vahel (kus NP-täielikud probleemid on keskmises tähenduses rasked, kuid krüptograafia on endiselt võimatu). See muudab probleemi, mida nad uurisid, peamiseks kandidaadiks Pessilandi ründamiseks ja nende jaoks värskemat tööd näitab, et see võib töötada ka Heuristica vastu.

"Erinevad pusletükid on puudu," ütles Pass. "Minu jaoks on lihtsalt maagiline, et need väljad on nii tihedalt seotud."

Hirahara hoiatab, et väljakutsed ootavad endiselt teadlasi, kes kavatsevad hävitada Impagliazzo 30 aastat tagasi välja võlutud maailmad. "Tahaksin öelda, et ühel hetkel on Heuristica ja Pessiland välistatud, kuid ma pole kindel, kui lähedal me oleme," ütles ta.

Paljud teadlased eeldavad, et suurimaks raskuseks on näiliselt kahjutu lõhe ületamine kahe erineva keskmise keerukuse mudeli vahel. Krüptograafid uurivad tavaliselt keskmiste juhtumite algoritme, mis teevad vigu mõlemas suunas, märkides juhuslikud stringid aeg-ajalt valesti pseudojuhuslikeks ja vastupidi. Samal ajal töötavad Hirahara halvima ja keskmise juhu vähendamised keskmiste juhtumite algoritmide puhul, mis teevad ainult esimest tüüpi vigu. Sellised peened eristused võivad keerukuse teoorias muuta maailma. Kuid vaatamata sellele ja paljudele teistele takistustele ei saa Allender jätta kõlama kaitstud optimismi.

"Püüan mitte lubada end liiga palju usklikuks jääda, sest seal on üsna väljakujunenud ajalugu, et miski ei tööta," ütles ta. "Kuid me näeme palju tõeliselt põnevaid arenguid - viise, kuidas ületada asju, mis näisid tõkkedena."

Kui on üks õppetund, mida teadlased on oma võitlusest P versus NP küsimusele vastamiseks või isegi lihtsalt mõistmiseks õppinud, on see, et keerukuse teooria on ise keeruline. Kuid just see väljakutse teeb otsingu nii rahuldust pakkuvaks.

"See on tegelikult omamoodi suurepärane, et see nii raske on," ütles Carmosino. "Mul ei hakka kunagi igav."

Toimetaja märkus: Scott Aaronson on liige Quanta Magazine'S nõuandev kogu.