Monimutkaisuusteorian 50 vuoden matka tiedon rajoihin | Quanta-lehti

Vuoden 2007 syyslukukauden ensimmäisellä viikolla Marco Carmosino vetäytyi matematiikan luokkaan, joka vaaditaan kaikille tietojenkäsittelytieteen pääaineille Massachusettsin yliopistossa Amherstissä. Toisen vuoden opiskelija Carmosino harkitsi lopettavansa yliopistosta suunnittelemaan videopelejä. Sitten professori esitti yksinkertaisen kysymyksen, joka muuttaisi hänen elämänsä kulun: Mistä tiedät, että matematiikka todella toimii?

"Se sai minut istumaan ja kiinnittämään huomiota", muisteli Carmosino, nykyään teoreettinen tietojenkäsittelytieteilijä IBM:llä. Hän ilmoittautui valinnaiseen seminaariin Kurt Gödelin työstä, jonka huimaavat itseviittausargumentit paljastivat ensin matemaattisen päättelyn rajat ja loivat pohjan kaikelle tulevalle laskennan perusrajoja koskevalle työlle. Siinä oli paljon otettavaa vastaan.

"En 100% ymmärtänyt", Carmosino sanoi. "Mutta tiesin, että haluan."

Nykyään jopa kokeneet tutkijat löytävät ymmärrystä pulasta, kun he kohtaavat teoreettisen tietojenkäsittelytieteen keskeisen avoimen kysymyksen, joka tunnetaan nimellä P vs. NP -ongelma. Pohjimmiltaan tämä kysymys kysyy, voidaanko monet pitkään äärimmäisen vaikeina pidetyt laskennalliset ongelmat todella ratkaista helposti (salaisen pikakuvakkeen kautta, jota emme ole vielä löytäneet), vai ovatko ne todella vaikeita, kuten useimmat tutkijat epäilevät. Vaakalaudalla ei ole vähempää kuin tiedossa olevan luonne.

Huolimatta tutkijoiden vuosikymmenten ponnisteluista laskennallisen monimutkaisuuden teorian alalla - tällaisten kysymysten tutkimisesta eri ongelmien luontaisista vaikeudesta - ratkaisu P vs. NP -kysymykseen on jäänyt vaikeaksi. Eikä ole edes selvää, mistä mahdollisen todisteen pitäisi alkaa.

"Ei ole tiekarttaa", sanoi Michael Sipser, kokenut kompleksisuusteoreetikko Massachusetts Institute of Technologysta, joka kamppaili vuosia ongelman kanssa 1980-luvulla. "On kuin olisit menossa erämaahan."

Vaikuttaa siltä, ​​että laskennallisten ongelmien vaikeuden ratkaiseminen on sinänsä vaikea tehtävä. Mutta miksi se on niin vaikeaa? Ja kuinka vaikeaa se on? Carmosino ja muut meta-kompleksin ala-alan tutkijat muotoilevat tällaiset kysymykset uudelleen laskennallisiksi ongelmiksi, jotka vievät alaa eteenpäin kääntämällä kompleksisuusteorian linssin takaisin itseensä.

"Saatat ajatella: 'OK, se on hienoa. Ehkä monimutkaisuusteoreetikot ovat tulleet hulluiksi", sanoi Rahul Ilango, MIT:n jatko-opiskelija, joka on tuottanut alan jännittävimpiä viimeaikaisia ​​tuloksia.

Näitä sisäänpäin suuntautuvia kysymyksiä tutkimalla tutkijat ovat oppineet, että laskennallisen kovuuden todistamisen kovuus on kiinteästi sidoksissa peruskysymyksiin, jotka saattavat aluksi tuntua liittymättömiltä. Kuinka vaikeaa on havaita piilotettuja kuvioita näennäisesti satunnaisissa tiedoissa? Ja jos todella vaikeita ongelmia on, kuinka usein ne ovat vaikeita?

"On käynyt selväksi, että meta-monimutkaisuus on lähellä asioiden ydintä", sanoi Scott Aaronson, monimutkaisuusteoreetikko Texasin yliopistossa Austinissa.

Tämä on tarina pitkästä ja mutkaisesta polusta, joka johti tutkijat P vs. NP -ongelmasta meta-monimutkaisuuteen. Se ei ole ollut helppo matka – polku on täynnä vääriä käännöksiä ja tiesulkuja, ja se kiertelee itseään yhä uudelleen ja uudelleen. Silti meta-monimutkaisuuden tutkijoille matka kartoittamattomaan maisemaan on oma palkkionsa. Aloita kysymällä näennäisesti yksinkertaisia ​​kysymyksiä, sanoi Valentine Kabanets, monimutkaisuusteoreetikko Simon Fraser -yliopistossa Kanadassa, ja "sinulla ei ole aavistustakaan, minne aiot mennä."

Tunnetut Tuntemattomat

P vs. NP -ongelma johtuu laimeasta nimestään monimutkaisuusteoreetikkojen tavasta lajitella laskennalliset ongelmat laajoiksi.monimutkaisuusluokat” Nasdaq-symboleihin viittaavilla tarroilla. Laskennallinen ongelma on sellainen, joka voidaan periaatteessa ratkaista algoritmilla – tarkasti määritellyllä ohjeluettelolla. Mutta kaikki algoritmit eivät ole yhtä hyödyllisiä, ja algoritmien väliset vaihtelut viittaavat perustavanlaatuisiin eroihin eri luokkien ongelmien välillä. Monimutkaisuusteoreetikkojen haasteena on muuttaa nämä vihjeet tiukoiksi lauseiksi kompleksisuusluokkien välisistä suhteista.

Nämä suhteet heijastavat muuttumattomia totuuksia laskennasta, jotka ylittävät paljon mitään tiettyä tekniikkaa. "Tämä on kuin maailmankaikkeuden lakien löytäminen", Kabanets sanoi.

"P" ja "NP" ovat kaksi tunnetuinta jäsentä a kasvava eläintarha sadoista monimutkaisuusluokista. Karkeasti sanottuna P on ongelmien luokka, jotka voidaan ratkaista helposti, kuten luettelon aakkosjärjestäminen. NP on ongelmaluokka, jossa on helposti tarkistettavia ratkaisuja, kuten sudoku-pulmia. Koska kaikki helposti ratkaistavissa olevat tehtävät ovat myös helppoja tarkistaa, ovat P:n tehtävät myös NP:ssä. Mutta jotkut NP-ongelmat näyttävät vaikeilta ratkaista – et voi heti intuitoida ratkaisua sudoku-pulmaan kokeillematta ensin monia mahdollisuuksia. Voisiko olla, että tämä näennäinen kovuus on vain illuusio - että jokaisen helposti tarkistettavan ongelman ratkaisemiseen on yksi yksinkertainen temppu?

Jos on, niin P = NP: Nämä kaksi luokkaa ovat ekvivalentteja. Jos näin on, täytyy olla jokin algoritmi, joka tekee valtavien sudokupulmien ratkaisemisen, maailmanlaajuisten toimitusreittien optimoinnin, huippuluokan salauksen rikkomisen ja matemaattisten lauseiden todisteiden automatisoinnin triviaaliksi. Jos P ≠ NP, niin monet periaatteessa ratkaistavissa olevat laskennalliset ongelmat jäävät käytännössä ikuisesti käsityksemme ulkopuolelle.

Tutkijat olivat huolissaan muodollisen matemaattisen päättelyn rajoista kauan ennen kuin P vs. NP -ongelma julkaistiin - todellakin kauan ennen modernin tietojenkäsittelytieteen alkua. Vuonna 1921 kamppaillessaan saman kysymyksen kanssa, joka kiinnitti Carmosinon huomion lähes vuosisataa myöhemmin, matemaatikko David Hilbert ehdotti tutkimusohjelmaa matematiikan perustamiseksi ehdottoman varmasti. Hän toivoi aloittavansa muutamista yksinkertaisista oletuksista, joita kutsutaan aksioomeiksi, ja johtavansa yhtenäisen matemaattisen teorian, joka täytti kolme keskeistä kriteeriä.

Hilbertin ensimmäinen ehto, johdonmukaisuus, oli olennainen vaatimus, että matematiikassa ei ole ristiriitoja: Jos kaksi ristiriitaista väitettä voitaisiin todistaa samoista aksioomeista, koko teoria olisi pelastamaton. Mutta teoria voisi olla ristiriitaton ja silti rajallinen. Tämä oli motivaatio Hilbertin toiselle ehdolle, täydellisyydelle: vaatimus, jonka mukaan kaikki matemaattiset väitteet ovat joko todistetusti tosia tai todistettavasti vääriä. Hänen kolmas kriteerinsä, päätettävyys, vaati yksiselitteistä mekaanista menettelyä sen määrittämiseksi, oliko jokin matemaattinen väite tosi vai epätosi. Vuonna 1930 konferenssissa pitämässään puheessa Hilbert julisti: "Sloganimme tulee olemaan 'Meidän täytyy tietää, me tulemme tietämään'."

Vain vuotta myöhemmin Gödel antoi ensimmäisen iskun Hilbertin unelmaan. Hän osoittautui että itseään tuhoava väite, kuten "tämä väite ei ole todistettavissa", voitaisiin johtaa mistä tahansa sopivasta aksioomijoukosta. Jos tällainen väite on todellakin todistamaton, teoria on epätäydellinen, mutta jos se on todistettavissa, teoria on epäjohdonmukainen - vielä huonompi tulos. Samassa paperissa Gödel osoitti myös, ettei mikään matemaattinen teoria voisi koskaan todistaa omaa johdonmukaisuuttaan.

Tutkijat toivoivat edelleen, että tuleva matematiikan teoria, vaikkakin välttämättä epätäydellinen, saattaa kuitenkin osoittautua ratkaisevaksi. Ehkä he voisivat kehittää menettelytapoja, jotka tunnistaisivat kaikki todistettavissa olevat lausunnot ja välttyisivät Gödelin kaltaisista kiusallisista ehdotuksista. Ongelmana oli, että kukaan ei osannut perustella näitä hypoteettisia menettelyjä.

Sitten vuonna 1936 23-vuotias jatko-opiskelija nimeltä Alan Turing muotoili uudelleen Hilbertin päätettävyysehdon tuolloin tuntemattomalla laskentakielellä ja antoi sille kohtalokkaan iskun. Turing muotoili matemaattisen mallin, joka tunnetaan nykyään nimellä Turingin kone — joka voisi edustaa kaikkia mahdollisia algoritmeja, ja osoitti, että jos Hilbertin menettely olisi olemassa, se sopisi tähän malliin. Sitten hän käytti itseviittausmenetelmiä, kuten Gödelin todistaa ratkaisemattomien lausumien olemassaolo – tai vastaavasti laskemattomia ongelmia, joita mikään algoritmi ei pystyisi ratkaisemaan.

Hilbertin ohjelma oli raunioina: ikuisesti olisi perustavanlaatuiset rajat sille, mitä voitaisiin todistaa ja mitä voitaisiin laskea. Mutta kun tietokoneet kehittyivät teoreettisista abstraktioista todellisiksi koneiksi, tutkijat ymmärsivät, että Turingin yksinkertainen ero ratkaistavien ja ratkaisemattomien ongelmien välillä jätti monia kysymyksiä vastaamatta.

1960-luvulle mennessä tietojenkäsittelytieteilijät olivat kehittäneet nopeita algoritmeja joidenkin ongelmien ratkaisemiseksi, kun taas toisille ainoat tunnetut algoritmit olivat tuskallisen hitaita. Entä jos kysymys ei olisi vain siitä, ovatko ongelmat ratkaistavissa, vaan kuinka vaikeita ne on ratkaista?

"Rikas teoria syntyy, emmekä tiedä enää vastauksia", Carmosino sanoi.

Erilaiset polut

Havainnollistaaksemme, kuinka hämmentäviä kovuutta koskevat kysymykset voivat olla, tarkastellaan paria läheisesti toisiinsa liittyvää ongelmaa, joihin liittyy kaavioita. Nämä ovat pisteiden verkkoja, joita kutsutaan solmuiksi ja jotka on yhdistetty viivoilla, joita kutsutaan reunoiksi. Tietojenkäsittelytieteilijät käyttävät niitä mallintaakseen kaiken kvanttilaskenta että liikenteen sujuvuus.

Oletetaan, että sinulle annetaan kaavio ja pyydetään löytämään jotain, jota kutsutaan Hamiltonin poluksi – reitti, joka kulkee jokaisen solmun läpi tarkalleen kerran. Tämä ongelma on periaatteessa selvästi ratkaistavissa: Mahdollisia polkuja on vain rajallinen määrä, joten jos mikään muu epäonnistuu, voit vain tarkistaa jokaisen. Se on hyvä, jos solmuja on vain muutama, mutta jopa hieman suuremmissa kaavioissa mahdollisuuksien määrä karkaa käsistä, mikä tekee tästä yksinkertaisesta algoritmista nopeasti hyödyttömän.

On olemassa kehittyneempiä Hamiltonin polkualgoritmeja, jotka taistelevat paremmin, mutta aika, jonka algoritmit vaativat ongelman ratkaisemiseen, kasvaa poikkeuksetta eksponentiaalisesti graafin koon mukaan. Kaavioiden ei tarvitse olla kovin suuria, ennen kuin parhaatkin algoritmitutkijat ovat havainneet, että ne eivät löydä polkua "kohtuullisessa ajassa", sanoi. Russell Impagliazzo, monimutkaisuusteoreetikko Kalifornian yliopistosta San Diegosta. "Ja "kohtuullisella ajalla" tarkoitan "ennen kuin maailmankaikkeus loppuu".

Hamiltonin polun ongelmalla on toinen mielenkiintoinen ominaisuus. Jos joku väittää löytäneensä Hamiltonin polun tietystä graafista, voit nopeasti tarkistaa, onko ratkaisu pätevä, vaikka graafi olisi erittäin suuri. Sinun tarvitsee vain seurata polkua ja rastittaa solmut yksitellen ja varmistaa, että et ole rastittanut yhtäkään solmua kahdesti. Jos lopusta ei puutu solmuja, polku on Hamiltonin.

Tämän ratkaisuntarkistusalgoritmin suorittamiseen tarvittava aika on verrannollinen kaavion kokoon. Tämä asettaa sen laajempaan polynomialgoritmien luokkaan, jonka suoritusajat kasvavat graafin koon polynomifunktioiden mukaan. Polynomikasvu on hillittyä eksponentiaaliseen kasvuun verrattuna, joten polynomialgoritmit säilyvät käyttökelpoisina myös suurilla graafisilla kaavioilla. "Se on dramaattisesti tehokkaampi", Carmosino sanoi.

Hamiltonin polun ongelmalla on jyrkkä epäsymmetria: Voit varmistaa oikean ratkaisun käyttämällä nopeaa polynomialgoritmia, mutta ratkaisun löytämiseen tarvitset hitaan eksponentiaalisen algoritmin. Tuo epäsymmetria ei ehkä vaikuta yllättävältä – on helpompi tunnistaa taiteellinen mestariteos kuin luoda sellainen, helpompi tarkistaa matemaattinen todistus kuin todistaa uusi lause – silti kaikilla laskennallisilla ongelmilla ei ole tätä epäsymmetristä luonnetta. Itse asiassa ongelma, joka on hyvin samanlainen kuin Hamiltonin polkujen löytäminen, käyttäytyy aivan eri tavalla.

Oletetaan, että sinulle annetaan jälleen graafi, mutta nyt sinua pyydetään löytämään "Eulerian polku", joka ylittää jokaisen reunan tarkalleen kerran. Jälleen on olemassa polynomialgoritmi mahdollisten ratkaisujen tarkistamiseen, mutta tällä kertaa ongelman ratkaisemiseen on myös polynomialgoritmi. Tässä ei ole epäsymmetriaa. Monimutkaisuusteoriassa jotkut polut näyttävät olevan helpompi löytää kuin toiset.

Sekä Hamiltonin polkuongelma että Eulerin polkuongelma ovat kompleksisuusluokkaa NP, joka on määritelty sisältämään kaikki ongelmat, joiden ratkaisut voidaan tarkistaa polynomialgoritmeilla. Eulerin polkuongelma kuuluu myös luokkaan P, koska polynomialgoritmi voi ratkaista sen, mutta joka tapauksessa se ei pidä paikkaansa Hamiltonin polun ongelmassa. Miksi näiden kahden graafisen ongelman, jotka ovat pinnallisesti samanlaisia, pitäisi erota niin dramaattisesti? Se on P vs. NP -ongelman ydin.

Universaalin kova

Aluksi monimutkaisuusluokat vaikuttivat käteviltä luokilta samankaltaisten mutta ei suoraan toisiinsa liittyvien ongelmien lajitteluun – kukaan ei epäillyt, että Hamiltonin polkujen löytämisellä olisi mitään tekemistä muiden kovien laskentaongelmien kanssa.

Sitten vuonna 1971, vuoden sisällä muuttamisesta Toronton yliopistoon sen jälkeen, kun häneltä evättiin virkakausi Yhdysvalloissa, monimutkaisuusteoreetikko Stephen Cook julkaistu poikkeuksellinen tulos. Hän tunnisti tietyn NP-ongelman oudolla piirteellä: Jos on polynomialgoritmi, joka voi ratkaista tämän ongelman, se voi ratkaista myös kaikki muut NP:n ongelmat. Cookin "yleinen" ongelma näytti olevan yksinäinen sarake, joka tuki ilmeisen vaikeiden ongelmien luokkaa ja erotti ne alla olevista helpoista ongelmista. Pura tuo yksi ongelma, niin loput NP:stä kaatuu.

Cook epäili, että hänen yleismaailmalliseen ongelmaansa ei ollut nopeaa algoritmia, ja hän sanoi saman verran lehden puolivälissä ja lisäsi: "Minusta tuntuu, että tämän olettamuksen todistamiseen kannattaa käyttää paljon vaivaa." "Huomattava vaiva" osoittautuisi vähättelyksi.

Samoihin aikoihin eräs jatko-opiskelija Neuvostoliitossa nimeltä Leonid Levin osoittautui a samanlainen tulos, paitsi että hän tunnisti useita erilaisia ​​yleismaailmallisia ongelmia. Lisäksi amerikkalainen kompleksisuusteoreetikko Richard Karp osoittautui että Cookin (ja Levinin, vaikka Karp ja Cook eivät tienneet Levinin työstä vasta vuosia myöhemmin) tunnistama universaalisuusominaisuus oli itsessään kaikkea muuta kuin universaali. Melkein jokaisella NP-tehtävällä ilman tunnettua polynomialgoritmia – eli lähes jokaisella helposti tarkistettavilla, vaikealta tuntuvalla ongelmalla – oli sama ominaisuus, joka tuli tunnetuksi NP-täydellisyydeksi.

Tämä tarkoittaa kaikkia NP-täydellisiä ongelmia - Hamiltonin polkuongelmaa, sudokut ja tuhansia muista — ovat täsmälleen samanarvoisia. "Teillä on kaikki nämä erilaiset luonnolliset tehtävät, ja ne kaikki taianomaisesti osoittautuvat samaksi tehtäväksi", Ilango sanoi. "Emme vieläkään tiedä, onko sama tehtävä mahdollinen vai ei."

Minkä tahansa NP-täydellisen ongelman vaikeuden ratkaiseminen riittäisi ratkaisemaan P vs. NP -kysymyksen. Jos P ≠ NP, helpon ja vaikeiden tehtävien eroa ylläpitävät tuhannet sarakkeet, jotka ovat kaikki yhtä vahvoja. Jos P = NP, koko rakennus horjuu romahduksen partaalla odottaen vain yhden palan putoamista.

Cook, Levin ja Karp olivat yhdistäneet monia toisiinsa liittymättömiä ongelmia. Nyt kompleksisuusteoreetikkojen täytyi vain ratkaista yksi ongelma: Onko P = NP vai ei?

Viisikymmentä vuotta myöhemmin kysymys on edelleen vailla vastausta. Kabanets vertasi laskennan rajoja koskevaa päättelyä laajan alueen kartoittamiseen ilman kokonaiskuvaa. Rajattoman laskentatehon omaava olento voisi kurkistaa alas vuoren huipulta ja ihailla koko maisemaa kerralla, mutta pelkkä kuolevainen ei voi luottaa sellaiseen etuun. "Ne meistä vuoren pohjalla voimme yrittää ehkä hypätä ylös ja alas saadakseen paremman näkymän", hän sanoi.

Oletetaan, että P = NP. Sen todistamiseksi tutkijoiden olisi löydettävä nopea algoritmi NP-täydelliselle ongelmalle, joka saattaa olla piilossa jossain epämääräisessä nurkassa tuon valtavan maiseman. Ei ole takeita siitä, että he löytävät sen pian: monimutkaisuusteoreetikot ovat joskus tehneet löysi nerokkaita algoritmeja näennäisesti vaikeisiin (vaikkakaan ei NP-täydellisiin) ongelmiin vasta vuosikymmenien työn jälkeen.

Oletetaan nyt, että P ≠ NP. Sen todistaminen tuntuu vielä vaikeammalta. Monimutkaisuusteoreetikot joutuisivat toteamaan, ettei nopeaa algoritmia voi olla olemassa, mikä ennakoi ja estää tehokkaasti kaikkien tulevien tutkijoiden parhaat ponnistelut.

Se, että ei tiedä mistä aloittaa, on osa ongelmaa. Mutta tutkijat eivät ole yrittäneet. Vuosikymmenten aikana he ovat hyökänneet ongelman kimppuun monesta näkökulmasta ja löytäneet polun tukkeutuneena joka käänteessä. "Se on yksi teoreettisen tietojenkäsittelytieteen räikeimmistä totuuksista", Carmosino sanoi. "Kun sinulla on ilmiö, joka on niin kestävä, haluat selityksen."

Carmosinon viimeiseen yliopistovuoteen mennessä hänen uteliaisuutensa oli johtanut hänet Gödelistä monimutkaisuusteorian jatkokurssille. Hän oli yllättynyt huomatessaan, että hän käyttää enemmän aikaa läksyihin kuin intohimoprojektiinsa, tietokoneohjelmaan, joka oppisi satujen kerrontarakenteen ja synnytti uusia.

"Ajattelin: "Vau, minun on otettava tämä vakavasti", Carmosino muisteli. Ennen pitkää hän oli niin uppoutunut aiheeseen, että hänen mentorinsa ehdotti lempeästi häntä harkitsemaan uudelleen valmistumisen jälkeisiä suunnitelmiaan.

"Hän sanoi:" Tiedätkö, jos haluat jatkaa tämän tekemistä, jos haluat jatkaa teoreettisen tietojenkäsittelytieteen ja monimutkaisuusteorian harjoittamista, voit: Sitä kutsutaan grad schooliksi', Carmosino sanoi. Saatuaan maisterintutkinnon hän muutti San Diegoon vuonna 2012 työskennelläkseen Impagliazzon ohjaaman tohtorin tutkinnon puolesta.

Carmosinon päätavoitteena oli aluksi ymmärtää paremmin a maamerkki paperi kahden vuosikymmenen ajalta, mikä oli valloittanut hänen mielikuvituksensa. Tuo paperi, monimutkaisuusteoreetikot Aleksanteri Razborov ja Steven Rudich, oli osoittanut, että tietty "luonnollinen" strategia todistaa P ≠ NP lähes varmasti epäonnistuisi, koska menestys maksaisi jyrkät kustannukset - salauksen täydellisen hajoamisen - jota tutkijat pitivät erittäin epätodennäköisenä. Tutkijat tulkitsevat Razborovin ja Rudichin tuloksen esteeksi tälle suositulle lähestymistavalle todistaa P ≠ NP.

Tämä "luonnollisten todisteiden este" on vain yksi monista tunnetuista esteistä avoimien ongelmien ratkaisemiselle kompleksisuusteoriassa. Jokainen toimii kuin tiesulku ja varoittaa, että lupaavalta näyttävä polku on itse asiassa umpikuja. Yhdessä nämä esteet osoittavat, että minkä tahansa todisteen, joka ratkaisee P vs. NP -ongelman, tulisi olla radikaalisti erilainen kuin minkään aiemmin käytetyn; Siksi useimmat tutkijat uskovat, että ratkaisu on kaukana. Mutta ainakin esteet kertovat heille, mistä ei saa etsiä.

"Monimutkaisuusteoria on sekä kirottu että siunattu niin monilla esteillä", Ilango sanoi.

Kun Carmosino kohtasi luonnollisten todisteiden esteen, se oli melkein 20 vuotta vanha. Mutta hän epäili, että sillä oli enemmän opetuksia tutkijoille. Tämä tunne vahvistuisi jonain päivänä, kun hän ja kolme kollegaa osoittivat yllättävän tuloksen tutkiessaan luonnollisten todisteiden estettä meta-kompleksisuuden näkökulmasta. Heidän todisteensa oli yksi harvoista merkittävistä tuloksista, jotka herättivät uutta kiinnostusta meta-monimutkaisuuteen, mikä johti edistyksen hurjaan viime vuosien aikana.

Mutta jotta voimme seurata polkua luonnollisten todisteiden esteestä meta-monimutkaisuuteen, meidän on palattava siihen, mihin jätimme tutkijat 1970-luvulla, jolloin he alkoivat käsitellä P vs. NP -ongelmaa. Mikä teki ongelmien todistamisesta niin vaikeaa?

Kiertoinen polku

Aluksi tutkijat yrittivät todistaa P ≠ NP – eli todistaa, että jotkin NP-ongelmat eivät ole ratkaistavissa millään mahdollisella polynomialgoritmilla – käyttämällä muunnelmia tekniikoista, joita Turing oli käyttänyt todistaakseen, että joitain ongelmia ei voida ratkaista millään algoritmilla. . Mutta he nopeasti löysi todiste siitä, että nuo menetelmät eivät toimisi – ensimmäinen suuri este P vs. NP -kysymyksen ratkaisemiselle. Niinpä he alkoivat etsiä toista lähestymistapaa, ja pian he löysivät sellaisen Turingin aikalaisen työstä Claude Shannon.

Shannon, joka varttui pienessä kaupungissa Pohjois-Michiganissa, vaikutti epätodennäköiseltä hahmolta tiedon aikakauden käynnistäjänä. Silti hän osoitti nousevan tietojenkäsittelytieteen monitieteisyyttä ja tunsi olevansa yhtä kotonaan sähkötekniikassa ja matemaattisessa logiikassa. Hänen Pro gradu tutkielma, Shannon osoitti, kuinka sähkömekaanisista kytkimistä tehdyt piirit voivat edustaa loogisia lausekkeita, jotka sisältävät Boolen muuttujia – suureita, jotka voivat ottaa vain kaksi arvoa (kuten tosi tai epätosi tai 1 ja 0).

Näissä lausekkeissa Boolen muuttujat on linkitetty toisiinsa "logiikkaporteilla" AND, OR ja EI. Esimerkiksi alkeislauseke A JA B on tosi, kun sekä A että B ovat tosi, ja epätosi muuten; A TAI B puolestaan ​​on tosi, jos ainakin toinen kahdesta muuttujasta on tosi. NOT-portti on vielä yksinkertaisempi: se kääntää yhden muuttujan arvon. Kun näitä perusrakennuspalikoita on riittävästi, voit suorittaa minkä tahansa laskennan.

"Kun katsot tietokonettasi päivän päätteeksi, mitä se tekee? Se pyörii radalla”, Ilango sanoi.

Shannonin työ ehdotti teoreetikoille uutta tapaa ajatella laskennallisten ongelmien vaikeutta, nimeltään "piirin monimutkaisuus", vaikka kyseessä olevat piirit ovatkin vain matemaattisia abstraktioita. Jonkin aikaa tutkijat ajattelivat, että tämä lähestymistapa voisi olla tapa ratkaista P vs. NP, mutta lopulta polku törmäsi luonnollisten todisteiden esteeseen.

Piirin monimutkaisuuskehys edellyttää Turingin laskentamallin peruskäsitteiden uudelleen miettimistä. Tässä laskennallisten ongelmien ja niitä ratkaisevien algoritmien sijaan tutkijat harkitsevat Boolen funktioita ja niitä laskevia piirejä. Boolen funktio ottaa Boolen muuttujat - tosi ja epätosi, 1s ja 0s - ja tulostaa joko tosi tai epätosi, 1 tai 0. Ja kuten algoritmi, piiri kuvaa proseduuria lähdön tuottamiseksi millä tahansa syötteellä.

"Ymmärrän, että ihmiset alkoivat työskennellä piirien monimutkaisuuden parissa, koska he päättivät, että Turingin koneet olivat liian monimutkaisia", sanoi Ryan Williams, monimutkaisuusteoreetikko MIT:ssä. "Voimme tutkia piirejä portti portilta."

Aivan kuten minkä tahansa laskennallisen ongelman ratkaisemiseen voi olla monia algoritmeja, joista toiset ovat nopeampia kuin toiset, monet erilaiset piirit voivat laskea minkä tahansa Boolen funktion, joissakin on vähemmän portteja kuin toisissa. Tutkijat määrittelevät funktion piirin monimutkaisuuden porttien kokonaismääräksi pienimmässä sen laskevassa piirissä. Funktiolle, jolla on kiinteä määrä tulomuuttujia, piirin monimutkaisuus on myös kiinteä luku – suurempi joillekin funktioille kuin muille.

Mutta monissa tapauksissa voit harkita monimutkaisempia versioita samasta funktiosta lisäämällä syötemuuttujien määrää, aivan kuten voit tehdä Hamiltonin polun ongelmasta vaikeamman ottamalla huomioon suurempia kuvaajia. Sitten tutkijat pohtivat samaa kysymystä, jota he kysyvät tutkiessaan algoritmin ajoaikoja: Kasvaako Boolen funktion laskemiseen tarvittava porttien vähimmäismäärä polynomiaalisesti vai eksponentiaalisesti, kun syöttömuuttujien määrä kasvaa? Tutkijat kutsuvat näitä kahta funktioluokkaa "helppo laskea" ja "vaikea laskea".

Helposti laskettava Boolen funktio on samanlainen kuin luokan P laskennallinen ongelma - ongelma, joka voidaan ratkaista polynomiajassa suoritettavalla algoritmilla. Mutta on myös kovia NP-ongelmia vastaavia toimintoja, joissa tutkijoiden paras tapa laskea asteittain suurempia versioita vaatii eksponentiaalisesti kasvavan porttien määrän, mutta vastaus voidaan kuitenkin helposti tarkistaa. Jos kompleksisuusteoreetikot voisivat todistaa, että ei todellakaan ole parempaa tapaa laskea tällaista funktiota, se merkitsisi P ≠ NP.

Tämä oli strategia, jota useimmat kompleksisuusteoreetikot noudattivat 1980-luvulla. Ja todennäköisyys oli heidän puolellaan. Shannonilla oli osoittautui vuonna 1949, että lähes jokaisessa Boolen totuustaulukossa (joka on vain pitkä lista kiinteäkokoisen Boolen funktion kaikista mahdollisista tuloista ja lähdöistä) on piirin monimutkaisuus, joka on käytännössä mahdollisimman korkea. Hän käytti hämmästyttävän yksinkertaista argumenttia: On paljon vähemmän tapoja yhdistää pieni määrä portteja kuin on tapoja yhdistää useita portteja.

"Ei vain ole tarpeeksi pieniä piirejä kiertääkseen", Aaronson sanoi.

Niinpä monimutkaisuusteoreetikot joutuivat omituiseen tilanteeseen. Jos lähes jokaisella totuustaulukolla on suuri piirin monimutkaisuus, niin lähes jokaisen Boolen funktion on oltava vaikea laskea. Tutkijoiden täytyi vain tunnistaa yksi tällainen toiminto, jonka tiedettiin myös kuuluvan luokkaan NP. Kuinka vaikeaa se voisi olla?

Crypto Bros

Aluksi kehitys oli nopeaa. Vuonna 1981 Sipser ja kaksi yhteistyökumppania osoittautui että tiettyä Boolen funktiota oli ehdottomasti vaikea laskea, jos he käyttivät piirejä tietyillä rajoituksilla porttien järjestämiselle.

"Fantasia oli, että pystyisit todistamaan asioita näistä rajoitetuista malleista ja sitten rakentamaan opitun pohjalta työskentelemään yhä harvemmilla rajoituksilla", Sipser sanoi.

Vuonna 1985 Razborov otti seuraavan suuren askeleen. Hän oli juuri aloittanut tutkijakoulun Moskovassa ja liittyi ponnisteluihin vahingossa käsitellessään ongelmaa toisella matematiikan alalla, jossa kävi ilmi, että P vs. NP -ongelman ratkaiseminen oli edellytys.

"Olin yksinkertaisesti onnekas, kun en tiennyt, kuinka vaikea tämä ongelma oli", Razborov sanoi. "Muuten en ehkä olisi edes aloittanut."

Razborov analysoi piirejä, jotka sisälsivät vain JA- ja TAI-portit, ja osoittautui että tiettyä funktiota oli vaikea laskea tällaisilla piireillä riippumatta siitä, kuinka portit oli järjestetty - mikä parasta, sen funktion tiedettiin olevan NP-täydellinen. Kaikki tutkijoiden täytyi ratkaista P vs. NP oli laajentaa Razborovin tekniikoita piireihin, joissa ei ole portteja.

"Oli eräänlainen universaali tunne, että yksi askel lisää, yksi isku ja me saamme sen", Razborov sanoi. Mutta niin ei käynyt. Razborov itse osoitti, että hänen menetelmänsä epäonnistuisi, ellei sekoitukseen lisättäisi portteja, eikä kukaan keksi muuta tietä eteenpäin. Vuosien kuluessa hän alkoi ihmetellä, miksi polku oli hiipunut.

Yhdysvalloissa Rudich pohti samaa kysymystä. Hän ja Impagliazzo olivat korkeakoululuokkatovereita, jotka olivat käyneet yhdessä tutkijakoulua. Heidän ystävyytensä oli saanut alkunsa yhteinen kiintymys Gödelin ja Turingin itseviittaustodistuksiin ja niiden vaikutuksiin matematiikan ja tietojenkäsittelytieteen perusteisiin.

"Vitsimme oli, että aiomme saada painikkeen, jossa lukee "itseviittaus", Impagliazzo sanoi.

Jatko-opiskelijina sekä Rudich että Impagliazzo työskentelivät kryptografian monimutkaisuusteoreettisten perusteiden parissa, aiheessa, joka tarjoaa ehkä parhaan käytännön motivaation yrittää todistaa P ≠ NP. Kryptografit kätkevät salaiset viestit peittämällä ne "pseudoratunnaisuuteen" – tällä tavalla salattu viesti näyttää satunnaiselta numerosekoitukselta kenelle tahansa salakuuntelijalle, mutta aiottu vastaanottaja voi silti purkaa sen. Mutta kuinka voit olla varma, että mahdollisen salakuuntelijan on liian vaikea murtaa koodi?

Tässä tulee esiin monimutkaisuusteoria. Nykyään yleisimmin käytetyt salausmenetelmät perustuvat kaikki näennäisesti koviin NP-ongelmiin – viestin salauksen purkamiseksi hyökkääjä tarvitsee vielä löytämättömän nopean algoritmin ongelman ratkaisemiseksi. Varmistaaksesi, että nämä menetelmät ovat todella turvallisia, sinun on todistettava, että P ≠ NP. Ilman todisteita, Sipser sanoi, voit vain "toivoa, että se, jolta yrität pitää salaisuuden, ei ole parempi matemaatikko kuin olet."

Vaikka kryptografia oli sinänsä kiehtovaa, se näytti olevan kaukana itseviittausargumenteista, jotka olivat ensin vetäneet Rudichin ja Impagliazzon alalle. Mutta kun Rudich kamppaili ymmärtääkseen, miksi piirin monimutkaisuus oli pysähtynyt, hän alkoi ymmärtää, etteivät nämä kaksi kohdetta olleet niin kaukana toisistaan. Strategiatutkijat olivat omaksuneet yrittäessään todistaa, että P ≠ NP:llä oli itseään tuhoava luonne, joka muistutti Gödelin kuuluisaa väitettä "tämä väite on todistamaton" - ja kryptografia voisi auttaa selittämään miksi. Venäjällä Razborov löysi samanlaisen yhteyden suunnilleen samaan aikaan. Nämä olivat luonnollisten todisteiden esteen siemeniä.

Luonnollisten todisteiden esteen ytimessä oleva jännitys on se, että tehtävä erottaa erittäin monimutkaisia ​​​​funktioita matalan monimutkaisuuden funktioista on samanlainen kuin tehtävä erottaa todellinen satunnaisuus viestien salaamiseen käytetystä näennäissatunnaisuudesta. Haluamme osoittaa, että korkean monimutkaisuuden funktiot ovat kategorisesti erilaisia ​​kuin matalan monimutkaisuuden funktiot, todistaaksemme P ≠ NP. Mutta haluaisimme myös, että näennäissatunnaisuutta ei voida erottaa sattumanvaraisuudesta, olla varmoja kryptografian turvallisuudesta. Ehkä emme voi saada sitä molempiin suuntiin.

Julma vitsi

Vuonna 1994 Razborov ja Rudich ymmärsivät, että he olivat saaneet samanlaisia ​​oivalluksia, ja he alkoivat työskennellä yhdessä tulosten yhdistämiseksi. He havaitsivat ensin, että kaikki aiemmat yritykset todistaa P ≠ NP käyttämällä piirin monimutkaisuutta, olivat omaksuneet saman yleisstrategian: Tunnista NP-täydellisen Boolen funktion erityinen ominaisuus ja todista sitten, ettei mikään helposti laskettava funktio voisi jakaa tätä ominaisuutta. Tämä osoittaisi, että valittu NP-täydellinen funktio oli todella vaikea laskea, mikä todistaa, että P ≠ NP.

Sipser, Razborov ja muut olivat käyttäneet tätä samaa strategiaa menestyksekkäästi todistaakseen rajallisemmat tulokset, ja joka tapauksessa tutkijoiden havaitsema erikoisominaisuus oli useimpien Boolen funktioiden yhteinen. Razborov ja Rudich loivat termin "luonnollinen todiste" viittaamaan tähän tapaukseen, jossa omaisuus oli laajalti jaettu, yksinkertaisesti siksi, ettei ollut tunnettua vaihtoehtoa. Jos "luonnolliset" todisteet olisivat mahdollisia, niiden olisi oltava hyvin ristiriitaisia ​​ja nimen arvoisia.

Razborov ja Rudich osoittivat sitten päätuloksensa: luonnollinen todiste P ≠ NP:stä vaatisi erittäin kattavan ymmärryksen siitä, kuinka helposti laskettavat ja vaikeasti laskettavat funktiot eroavat toisistaan, ja että tieto voisi myös ruokkia nopeaa algoritmia helpon havaitsemiseen. -laskea funktioita, vaikka ne olisivat pinnallisesti monimutkaisia. Jos kompleksisuusteoreetikot olisivat onnistuneet P ≠ NP:n luonnollisessa todistuksessa, he olisivat löytäneet lähes erehtymättömän tavan katsoa mielivaltaista totuustaulukkoa ja määrittää, onko vastaavalla funktiolla korkea vai alhainen piirin monimutkaisuus – paljon vahvempi ja yleisempi tulos kuin he olivat ryhtyneet todistamaan.

"Et melkein voi olla saamatta enemmän kuin olette neuvotelleet", Carmosino sanoi.

On kuin olisit yrittänyt tarkistaa faktat tietyn väitteen osalta, mutta jokainen yritys muuttui yleiskäyttöisen valheenpaljastimen suunnitelmaksi – se vaikuttaisi liian hyvältä ollakseen totta. Monimutkaisuusteoreetikoille luonnollisten todisteiden yllättävä voima teki menestyksen myös epätodennäköiseltä. Mutta jos tällainen todiste olisi onnistunut, odottamattomat seuraukset olisivat huonoja uutisia kryptografialle piirin monimutkaisuuden ja näennäissatunnaisuuden välisen yhteyden vuoksi.

Ymmärtääksesi tämän yhteyden, kuvittele katsovasi Boolen funktion totuustaulukon tulossaraketta, jossa on useita syötemuuttujia, ja korvaat jokaisen "true" luvulla 1 ja jokainen "false" 0:lla:

Jos Boolen funktiolla on suuri piirin monimutkaisuus, tuota pitkää ulostuloluetteloa ei periaatteessa voida erottaa todella satunnaisesta 0:n ja 1:n merkkijonosta, joka saadaan esimerkiksi kolikon heittämisellä toistuvasti. Mutta jos funktiolla on pieni piirin monimutkaisuus, merkkijonolla on oltava yksinkertainen, ytimekäs kuvaus, vaikka se näyttää monimutkaiselta. Tämä tekee siitä hyvin samanlaisen kuin salaustekniikassa käytetyt näennäissatunnaiset merkkijonot, joiden ytimekäs kuvaus on salainen viesti, joka on haudattu tuohon näennäiseen satunnaisuuteen.

Joten Razborovin ja Rudichin tulos osoitti, että mikä tahansa luonnollinen todiste P ≠ NP antaisi myös nopean algoritmin, joka voisi erottaa piilosatunnaiset merkkijonot, jotka sisältävät piiloviestejä, todella satunnaisista. Turvallinen kryptografia olisi mahdotonta – juuri päinvastoin kuin mitä tutkijat toivoivat saavansa selville todistamalla P ≠ NP.

Toisaalta, jos turvallinen kryptografia on mahdollista, luonnolliset todisteet eivät ole käyttökelpoinen strategia todistaa P ≠ NP — turvallisen kryptografian edellytys. Se on luonnollinen todisteiden este pähkinänkuoressa. Näytti siltä, ​​että monimutkaisuusteoreetikot olivat julman vitsin vastaanottajan päässä.

"Jos uskot kovuuteen, sinun pitäisi uskoa, että kovuutta on vaikea todistaa", Kabanets sanoi.

Metaverssiin

Tämä yhteys P ≠ NP -oletuksen implikaatioiden ja sen todistamisvaikeuden välillä oli kiehtova, mutta hankala selvittää. Ensinnäkin luonnollisten todisteiden este esti vain yhden lähestymistavan todistaa P ≠ NP. Toisaalta se yhdisti vaikeuden todistaa P ≠ NP ei itse P ≠ NP: hen, vaan turvallisen kryptografian olemassaoloon - läheisesti liittyvään mutta ei aivan vastaavaan ongelmaan. Ymmärtääkseen yhteyden todella, tutkijoiden olisi kohdattava meta-monimutkaisuus.

"On tämä intuitio, että "oi, koska P ≠ NP, on vaikea todistaa, että P ≠ NP", Williams sanoi. "Mutta saadaksesi edes järkeä tästä intuitiosta, sinun on alettava ajatella tehtävää todistaa jotain, kuten P ≠ NP, laskennalliseksi ongelmaksi."

Sitä Kabanets teki jatko-opiskelijana. Hän oli kasvanut Ukrainassa ja päätti tietojenkäsittelytieteen perustutkinto-opinnot kaksi vuotta Neuvostoliiton hajoamisen jälkeen. Sitä seuranneessa myllerryksessä hänellä ei ollut juurikaan mahdollisuuksia käsitellä häntä eniten kiinnostavia teoreettisia aiheita.

"Halusin tehdä jotain akateemisempaa", Kabanets muisteli. "Ja olin myös utelias näkemään maailmaa." Hän muutti Kanadaan tutkijakoulua varten, ja siellä hän oppi luonnollisten todisteiden esteestä. Kuten Carmosino, Kabanets oli ihastunut tulokseen. "Vaikutti hyvin syvältä, että teillä on tämä yhteys", hän sanoi.

Vuonna 2000, kun hänen opiskeluaikansa loppui, hän huomasi, että luonnollinen todisteiden este nousi jatkuvasti esiin hänen keskusteluissaan Jin-Yi Cai, monimutkaisuusteoreetikko, joka vieraili Torontossa tuolloin sapattivapaalla. He eivät alkaneet nähdä estettä tiesulkuna vaan kutsuna – tilaisuutena tutkia tarkasti, kuinka vaikeaa oli osoittaa ongelmien vaikeaksi. The paperi jossa he esittelivät tämän uuden näkökulman, siitä tulisi yksi vaikutusvaltaisimmista varhaisista teoksista meta-kompleksisuuden syntymässä.

Kabanetsin ja Cain artikkelissa korostettiin laskennallista ongelmaa, joka liittyy implisiittisesti Razborovin ja Rudichin luonnollisten todisteiden esteen muotoiluun: Kun otetaan huomioon Boolen funktion totuustaulukko, määritä, onko sillä korkea vai alhainen piirin monimutkaisuus. He kutsuivat tätä minimipiirikoon ongelmaksi tai MCSP:ksi.

MCSP on pohjimmainen meta-kompleksisuusongelma: laskennallinen ongelma, jonka aiheena ei ole graafiteoria tai muu ulkopuolinen aihe, vaan itse kompleksisuusteoria. Itse asiassa se on kuin kvantitatiivinen versio kysymyksestä, joka sai kompleksisuusteoreetikot käsittelemään P:tä vastaan ​​NP:tä käyttämällä piirin monimutkaisuuden lähestymistapaa 1980-luvulla: Mitä Boolen funktioita on vaikea laskea ja mitkä ovat helppoja?

"Jos keksisimme MCSP-algoritmin, se olisi kuin tapa automatisoida mitä teemme monimutkaisuusteoriassa", Impagliazzo sanoi. "Sen pitäisi ainakin antaa meille valtava käsitys siitä, kuinka voimme tehdä työmme paremmin."

Monimutkaisuusteoreetikot eivät välitä siitä, että tämä maaginen algoritmi saa heidät työttömäksi – he eivät usko, että sitä on ollenkaan, koska Razborov ja Rudich osoittivat, että mikä tahansa algoritmi, jolla voidaan erottaa erittäin monimutkaisia ​​totuustaulukoita matalan monimutkaisuuden taulukoista, tekisi salauksen. mahdotonta. Tämä tarkoittaa, että MCSP on todennäköisesti vaikea laskennallinen ongelma. Mutta kuinka vaikeaa se on? Onko se NP-täydellinen, kuten Hamiltonin polun ongelma ja lähes kaikki muut ongelmat, joiden kanssa tutkijat kamppailivat 1960-luvulla?

NP:n ongelmille "kuinka vaikeaa se on?" on yleensä tarpeeksi helppo vastata, mutta MCSP vaikutti oudolta poikkeavalta. "Meillä on hyvin vähän "kelluvia" ongelmia, jotka eivät ole liittyneet tähän NP-täydellisten ongelmien saareen, vaikka ne näyttävätkin vaikeilta", Kabanets sanoi.

Kabanets tiesi, että hän ja Cai eivät olleet ensimmäiset, jotka pohtivat ongelmaa, jota he olivat kutsuneet MCSP:ksi. Neuvostoliiton matemaatikot olivat tutkineet hyvin samanlaista ongelmaa 1950-luvulta lähtien yrittäessään varhaisessa vaiheessa ymmärtää erilaisten laskentaongelmien luontaista vaikeutta. Leonid Levin oli paininut sen kanssa kehittäessään NP-täydellisyyden teoriaa 1960-luvun lopulla, mutta hän ei pystynyt todistamaan sitä NP-täydellisiksi, ja hän julkaisi tärkeän artikkelinsa ilman sitä.

Sen jälkeen ongelma herätti vain vähän huomiota 30 vuoden ajan, kunnes Kabanets ja Cai huomasivat sen yhteyden luonnollisten todisteiden esteeseen. Kabanets ei odottanut ratkaisevansa kysymystä itse – sen sijaan hän halusi tutkia, miksi oli ollut niin vaikeaa todistaa, että tämä näennäisesti vaikea laskennallisen kovuuden ongelma oli todella vaikea.

"Se on tietyssä mielessä meta-meta-monimutkaisuus", sanoi Rahul Santanam, monimutkaisuusteoreetikko Oxfordin yliopistosta.

Mutta oliko se kovuus koko matkan alaspäin vai oliko ainakin jokin tapa ymmärtää, miksi tutkijat eivät olleet onnistuneet todistamaan, että MCSP oli NP-täydellinen? Kabanets havaitsi, että kyllä, siihen oli syy: piirin monimutkaisuuden ymmärtämisen vaikeus toimii esteenä mille tahansa tunnetulle strategialle, jolla todistetaan MCSP:n NP-täydellisyys - ongelma, joka itsessään liittyy piirin monimutkaisuuden ymmärtämisen vaikeuteen. Luonnollisten todisteiden esteen kierretty, itseään tuhoava logiikka vaikutti väistämättömältä.

On myös mahdollista, että MCSP ei ole NP-täydellinen, mutta sekin näyttää epätodennäköiseltä - ongelman tiettyjen yksinkertaisempien muunnelmien tiedetään jo olevan NP-täydellinen.

"Meillä ei vain ole mukavaa paikkaa laittaa sitä, joka suoraan liittyisi kaikkiin muihin tutkimiimme ongelmiin", Impagliazzo sanoi.

Kabanets oli valaisenut MCSP:n oudon käytöksen, mutta hän ei tiennyt kuinka edistyä. Meta-monimutkaisuuden tutkimus hidastui. Se kukoisti jälleen 16 vuotta myöhemmin, kun tutkijat löysivät yllättävän yhteyden toiseen peruskysymykseen: Kuinka vaikeaa on ratkaista ongelmia, jos välität vain oikean vastauksen saamisesta suurimman osan ajasta?

Maailmojen sota

Arjen ongelmiin useimmiten toimivat vastaukset riittävät usein. Suunnittelemme työmatkamme esimerkiksi tyypillisten liikennemuotojen mukaan, emme pahimpien skenaarioiden mukaan.

Useimpia monimutkaisuusteoreetikoja on vaikeampi tyydyttää: he tyytyväisiä julistavat ongelman helpoksi vain, jos he löytävät nopean algoritmin, joka saa oikean vastauksen jokaiseen mahdolliseen syötteeseen. Tämä standardi lähestymistapa luokittelee ongelmat sen mukaan, mitä tutkijat kutsuvat "pahimman tapauksen" monimutkaisuuteen. Mutta on olemassa myös "keskimääräisen tapauksen" monimutkaisuuden teoria, jossa ongelmia pidetään helpoina, jos on nopea algoritmi, joka saa oikean vastauksen useimmille syötteille.

Ero on tärkeä kryptografeille. Kuvittele laskennallinen ongelma, joka on helppo ratkaista lähes jokaiselle syötteelle, lukuun ottamatta muutamia itsepäisiä tapauksia, joissa paras algoritmi epäonnistuu. Pahimman tapauksen monimutkaisuusteoria pitää sitä vaikeana ongelmana, mutta kryptografian kannalta se on hyödytön: Jos vain osa viesteistäsi on vaikeasti tulkittavissa, mitä järkeä sillä on?

Itse asiassa Levin aloitti keskimääräisen tapauksen monimutkaisuuden tarkan tutkimuksen kymmenen vuotta hänen uraauurtavansa NP-täydellisyyttä koskevan työnsä jälkeen. Välivuosina hän oli joutunut sotkemaan neuvostoviranomaisia ​​– hän oli kunnioittamaton häirintä, joka ajoittain heikensi isänmaallista toimintaa kommunistisen puolueen nuorisoryhmässä. Vuonna 1972 häneltä evättiin tohtorin tutkinto nimenomaisista poliittisista syistä.

"Menestyäkseen Neuvostoliitossa nuorena tutkijana et voinut olla kovin mielistelevä, ja on vaikea kuvitella, ettei Leonid olisi mielisairas", Impagliazzo sanoi.

Levin muutti Yhdysvaltoihin vuonna 1978, ja 1980-luvun puolivälissä hän kiinnitti huomionsa keskimääräiseen tapausten monimutkaisuuteen. Hän aloitti työskentelyn muiden kanssa kehittääkseen teoriaa edelleen, mukaan lukien Impagliazzo, tuolloin jatko-opiskelija. Mutta vaikka he edistyivätkin, Impagliazzo havaitsi, että tutkijat puhuivat usein toistensa ohi. Hän halusi saada kaikki samalle sivulle, eikä se auttanut, että Levinin paperit olivat tunnetusti ytimekkäitä – se, joka aloitti kentän keskimääräisen tapauksen monimutkaisuus oli alle kaksi sivua pitkä.

"Aioin tehdä Leonidin työn käännöksen helpommin saavutettaviksi teknisiksi termeiksi", Impagliazzo sanoi. Hän päätti aloittaa lyhyellä, leikkisällä yleiskatsauksella ennen kuin sukeltaa matematiikkaan. "Tällainen valtasi paperin, ja se on ainoa osa, jonka kukaan muistaa."

- paperiVuonna 1995 julkaistusta julkaisusta tuli välitön klassikko. Impagliazzo loi hassuja nimiä viisi maailmaa jotka erottuvat erilaisten laskennallisten kovuusasteista ja erilaisista salausominaisuuksista. Elämme yhdessä näistä maailmoista, mutta emme tiedä missä.

Siitä lähtien, kun Impagliazzon artikkeli ilmestyi, tutkijat ovat haaveilleet osien eliminoimisesta hänen pienoismultiversumistaan ​​- kaventaa mahdollisuuksien tilaa todistamalla, että jotkin maailmoista eivät ole mahdollisia. Kaksi maailmaa ovat erityisen houkuttelevia kohteita: ne, joissa salaus on mahdotonta, vaikka P ≠ NP.

Yhdessä näistä maailmoista, nimeltään Heuristica, kaikki NP-täydelliset ongelmat on helppo ratkaista useimmilla syötteillä, mutta nopeat algoritmit tekevät toisinaan virheitä, joten näitä ongelmia pidetään edelleen vaikeina pahimman mahdollisen monimutkaisuusteorian standardien mukaan. Tämä on maailma, jossa salaus on mahdotonta, koska melkein jokainen koodi murtuu helposti. Toisessa maailmassa, nimeltään Pessiland, kryptografia on mahdotonta eri syystä: Jokainen ongelma on vaikea keskimääräisessä merkityksessä, mutta viestin salaus tekee siitä lukukelvottoman edes aiotulle vastaanottajalle.

Nämä kaksi maailmaa osoittavat olevan läheisesti sidoksissa meta-monimutkaisuusongelmiin – erityisesti Heuristican kohtalo liittyy pitkään jatkuneeseen kysymykseen siitä, onko MCSP NP-täydellinen. Kysymys, joka kiehtoi Kabanetsia ja järkytti Leviniä niin kauan sitten, ei ole pelkkä uteliaisuus: vaakalaudalla on koko maailma.

Heuristican sulkemiseksi pois tutkijoiden olisi tehtävä ero pahimman ja keskimääräisen tapauksen monimutkaisuuden välillä – toisin sanoen heidän on todistettava, että mikä tahansa hypoteettinen algoritmi, joka ratkaisee NP-täydellisen ongelman oikein useimmilla syötteillä, voi todella ratkaista sen. kaikissa tapauksissa. Tämänkaltainen yhteys, jota kutsutaan pahimmasta tapauksesta keskiarvoon, tiedetään olevan olemassa tietyissä ongelmissa, mutta mikään niistä ei ole NP-täydellinen, joten nämä tulokset eivät tarkoita mitään yleisempää. Heuristican poistaminen vie kryptografit puolitiehen toteuttamaan unelmansa turvallisesta salauksesta, joka perustuu siihen yhteen oletukseen, että P ≠ NP.

Mutta maailman tuhoaminen ei ole pieni saavutus. Vuonna 2003 kaksi kompleksisuusteoreetikot osoittivat että olemassa olevat lähestymistavat todistaakseen pahimmasta tapauksesta keskimääräiseen vähennykseen tunnetuissa NP-täydellisissä ongelmissa merkitsivät outoja seurauksia, mikä viittaa siihen, että tällaiset todisteet eivät todennäköisesti ole mahdollisia.

Tutkijoiden olisi löydettävä toinen lähestymistapa, ja he ajattelevat nyt, että MCSP saattaa olla juuri heidän tarvitsemansa ongelma. Mutta se ei selviä yli kymmeneen vuoteen. Ensimmäinen välähdys yhteydestä syntyi Marco Carmosinon jatkuvasta kiintymyksestä luonnollisten todisteiden esteeseen.

Carmosino kohtasi ensimmäisen kerran meta-kompleksitutkimuksen jatko-opiskelijana a 2013 paperi Kabanets ja neljä muuta tutkijaa, jotka kehittivät edelleen lähestymistapaa luonnollisten todisteiden esteeseen, jonka Kabanets oli uranuurtanut yli kymmenen vuotta aiemmin. Se vain vahvisti hänen vakaumustaan ​​siitä, että Razborovin ja Rudichin klassikkopaperista oli vielä opittavaa.

"Olin pakkomielle tuohon paperiin tuolloin", Carmosino sanoi. "Mikään ei ole muuttunut."

Pakkomielle kantoi lopulta hedelmää vieraillessaan lukukauden mittaisessa työpajassa Kalifornian yliopistossa Berkeleyssä, jossa hän vietti suurimman osan ajastaan ​​puhuen Impagliazzon, Kabanetsin ja Antonina Kolokolova, monimutkaisuusteoreetikko Memorial University of Newfoundlandissa, joka oli tehnyt yhteistyötä Kabanetsin kanssa vuoden 2013 artikkelissa. Carmosino oli työskennellyt heidän kolmen kanssaan kerran aiemmin, ja onnistunut yhteistyö antoi hänelle itseluottamusta pohtia heitä kysymyksiä aiheesta, joka kiehtoi häntä eniten.

"Hän kiusasi ihmisiä hyvällä tavalla", Kabanets muisteli.

Aluksi Carmosinolla oli uusia ideoita NP-täydellisyyden todistamiseksi MCSP:n versiolle, joka oli ilmestynyt Razborovin ja Rudichin luonnollista todistusta koskevassa tutkimuksessa. Mutta ne ideat eivät toteutuneet. Sen sijaan Impagliazzon varsinainen huomautus sai neljä tutkijaa ymmärtämään, että luonnollinen todisteiden este voisi tuottaa tehokkaampia algoritmeja kuin kukaan oli tajunnut – tiesulkuun oli kaiverrettu salainen kartta.

Jonkin sisällä 2016 paperi, neljä tutkijaa osoittivat, että tietynlaista keskimääräistä MCSP-algoritmia voitaisiin käyttää pahimman tapauksen algoritmin luomiseen satunnaisen näköisiin numerosarjoihin piilotettujen kuvioiden tunnistamiseen – tehtävään, jota tietojenkäsittelytieteilijät kutsuvat "oppimiseksi". Se on silmiinpistävä tulos, koska intuitiivisesti oppiminen näyttää vaikeammalta kuin MCSP-algoritmin suorittama binääriluokittelutehtävä - erittäin monimutkainen tai pieni monimutkaisuus. Ja yllättäen se yhdisti yhden tehtävän pahimman tapauksen monimutkaisuuden toisen tehtävän keskimääräiseen monimutkaisuuteen.

"Ei ollut ilmeistä, että tällaista yhteyttä olisi olemassa ollenkaan", Impagliazzo sanoi.

Nopea MCSP-algoritmi on puhtaasti hypoteettinen yleisille Boolen piireille: Se ei voi olla olemassa, ellei MCSP osoittautuu helpoksi laskennalliseksi ongelmaksi huolimatta kaikista päinvastaisista todisteista, ja tämä tarkoittaa, että neljän tutkijan artikkelin sisältämä oppimisalgoritmi on yhtä hypoteettinen.

Mutta joissakin MCSP:n yksinkertaisemmissa versioissa – monimutkaisten totuustaulukoiden erottaminen matalan monimutkaisuuden totuustaulukoista, kun piireille on erityisiä rajoituksia – nopeat algoritmit ovat olleet tunnettuja monta vuotta. Carmosinon, Impagliazzon, Kabanetsin ja Kolokolovan artikkeli osoitti, että nämä algoritmit voidaan muuntaa oppimisalgoritmeiksi, jotka olivat samoin rajoitettuja, mutta silti tehokkaampia kuin mikään, jonka tutkijat olivat aiemmin ymmärtäneet niin tiukasti teoreettisella tasolla.

"Jotinkin niiden itseään viittaava maku mahdollistaa sen, että voit tehdä asioita, joita et näennäisesti voi tehdä tavallisemmilla ongelmilla", Ilango sanoi.

Tulos kiinnitti muiden aiheiden parissa työskentelevien monimutkaisuusteoreetikojen huomion. Se oli myös esikatselu tulevien vuosien aikana ilmenevistä lisäyhteyksistä meta-monimutkaisuuden ja keskimääräisen tapauksen monimutkaisuuden välillä.

Ennen kaikkea se oli osoitus siitä, kuinka pitkälle tutkijat voivat päästä esittämällä yksinkertaisia ​​kysymyksiä esteistä, jotka aluksi näyttävät vain estävän heidän edistymistään.

"Tällainen kaksinaisuus on ollut teemana ainakin viimeisten 30 tai 40 monimutkaisuuden vuoden ajan", Impagliazzo sanoi. "Esteet ovat usein mahdollisuuksia."

Osittainen luotto

Edistys on vain kiihtynyt vuosien aikana sen jälkeen, kun Carmosino ja hänen kollegansa julkaisivat artikkelinsa.

"Uusia asioita tapahtuu", Kolokolova sanoi. "On paljon todella, todella taitavia nuorempia tutkijoita."

Ilango on yksi näistä nuorista tutkijoista – kolmen ensimmäisen tutkijakouluvuotensa aikana hän hyökkäsi pelottavaan avoimeen ongelmaan osoittaa MCSP:n NP-täydellinen käyttämällä kaksitahoista strategiaa: NP-täydellisyyden todistaminen yksinkertaisempi versiot MCSP:stä, kuten piirin monimutkaisuuden tutkijat tekivät hyökkääessään P:tä vastaan ​​NP:tä vastaan ​​1980-luvulla, samalla kun he osoittivat NP-täydellisyyden monimutkaisempia versioita, jotka vaikuttavat intuitiivisesti vaikeammilta ja ovat siten ehkä helpompi todistaa koviksi.

Ilango luottaa kiinnostuksensa meta-monimutkaisuuteen Eric Allender, Rutgersin yliopiston kompleksisuusteoreetikko ja yksi harvoista tutkijoista, jotka jatkoivat meta-kompleksisuuden parissa 2000-luvulla ja 2010-luvun alussa. "Hänen innostuksensa oli tarttuvaa", Ilango sanoi.

Toinen Allenderin inspiroima nuori tutkija on Shuichi Hirahara, nykyään professori Tokion National Institute of Informaticsissa. Vielä jatko-opiskelijana vuonna 2018 Hirahara paljasti Carmosinon ja hänen kirjoittajiensa löytämän meta-monimutkaisuuden ja tapausten keskimääräisen monimutkaisuuden välisen suhteen todellisen laajuuden. Nämä neljä tutkijaa olivat löytäneet yhteyden yhden ongelman – MCSP:n – keskimääräisen monimutkaisuuden ja toisen – Boolen oppimisen – pahimman tapauksen monimutkaisuuden välillä. Hirahara kehitti heidän tekniikoitaan edelleen ajelehtia MCSP:n pahimmasta tapauksesta keskiarvoon. Hänen tuloksensa viittaa siihen, että hypoteettinen keskimääräinen MCSP-algoritmi, kuten Carmosino ja hänen kollegansa ajattelivat, olisi itse asiassa tarpeeksi tehokas ratkaisemaan hieman erilainen MCSP-versio tekemättä virheitä.

Hiraharan tulos on jännittävä, koska monet tutkijat epäilevät, että MCSP on NP-täydellinen, toisin kuin kaikki muut ongelmat, joiden osalta tunnetaan pahimmasta tapauksesta keskimääräiseen tapaukseen liittyvät vähennykset. Jos he voivat laajentaa Hiraharan tulokset kattamaan kaikki keskimääräiset tapausalgoritmit ja sitten todistaa, että MCSP on NP-täydellinen, se osoittaisi, että emme elä Heuristicassa.

"Se olisi todella maata järisyttävä tulos", Santhanam sanoi.

Todistaminen, että MCSP on NP-täydellinen, voi tuntua raskaalta tilaukselta - loppujen lopuksi kysymys on ollut avoinna yli 50 vuotta. Mutta a jälkeen läpimurto Viime vuonna Hirahara, tutkijat ovat nyt paljon lähempänä kuin kukaan olisi odottanut muutama vuosi sitten.

Hirahara osoitti NP-täydellisyyden ongelman muunnelmassa, jota kutsutaan osittaiseksi MCSP:ksi, jossa jätät huomioimatta jokaisen totuustaulukon tietyt merkinnät. Hänen todisteensa perustui Ilangon kehittämiin menetelmiin osoittaakseen, että osittainen MCSP vastasi näennäisesti toisiinsa liittymätöntä ongelmaa, joka koski salaustekniikkaa nimeltä salainen jakaminen. Tämä on tapa jakaa salattu viesti useiden ihmisten kesken niin, että se voidaan purkaa vain, jos tietty osa heistä toimii yhdessä.

Mitä tahansa todellista kryptografiasovellusta varten haluat tietää tämän murto-osan etukäteen, mutta ylimääräisten kryptografisten temppujen avulla voit rakentaa turhauttavan skenaarion, jossa on vaikea vain selvittää, kuinka monen ihmisen on tehtävä yhteistyötä. Hirahara löysi tavan todistaa, että tämä keksitty kryptografinen ongelma oli NP-täydellinen, ja sitten osoitti, että todiste merkitsi myös osittaisen MCSP:n NP-täydellisyyttä.

Tämä tulos innosti meta-monimutkaisuuden tutkijoita jopa enemmän kuin Hiraharan aikaisemmat työt, ja muutkin tutkijat huomasivat sen – kompleksisuusteoreetikko ja bloggaaja Lance Fortnow kutsui sitä vuoden tulos. Tämä johtuu siitä, että tällaisten laskennallisten ongelmien "osittaisfunktioiden" versioiden käsitteleminen on ollut keskeinen välivaihe muissa NP-täydellisyyden todisteissa.

"Se on uskomatonta työtä", Williams sanoi. "Kaikki ajattelivat, että nämä osittaiset ongelmat olivat suunnilleen saman vaikeus kuin koko ongelma."

MCSP:n täyden version NP-täydellisyyden todistamisessa on edelleen esteitä. Mutta mikään ei ole sellaisia ​​esteitä, jotka viittaavat siihen, että kokonaan uusi työkalupakki tarvitaan – kyse voi olla vain oikean tavan löytämisestä tunnettujen tekniikoiden yhdistämiseen. Todistus ratkaisisi lopulta yhden niistä harvoista ongelmista, jotka ovat vastustaneet luokittelua niin kauan kuin monimutkaisuusteoria on ollut olemassa. Levin kirjoitti sähköpostitse: "Nöyrtyisin osoittamaan olevani tyhmä, kun en nähnyt sitä :-)."

Kadonneet osat

MCSP ei ole edes ainoa meta-monimutkaisuusongelma, joka on johtanut suureen läpimurtoon. Vuonna 2020 Cornell Techin kryptografi Rafael Pass ja hänen jatko-opiskelijansa Yanyi Liu löysi yhteyden erilaisen meta-monimutkaisuusongelman ja perustavanlaatuisen salausprotokollan välillä, joka määrittää rajan Heuristican ja Pessilandin, Impagliazzon pahimman maailmojen välillä (jossa NP-täydelliset ongelmat ovat vaikeita keskimääräisessä merkityksessä, mutta salaus on silti mahdotonta). Tämä tekee heidän tutkimastaan ​​ongelmasta parhaan ehdokkaan Pessilandin hyökkäykselle ja heidän tuoreempi työ osoittaa, että se voisi toimia myös Heuristicaa vastaan.

"Eri palapelin palaset puuttuvat", Pass sanoi. "Minulle on vain maagista, että nämä kentät liittyvät niin läheisesti toisiinsa."

Hirahara varoittaa, että haasteet odottavat edelleen tutkijoita, jotka aikovat lopettaa Impagliazzon 30 vuotta sitten loihtiman maailman. "Haluaisin sanoa, että jossain vaiheessa Heuristica ja Pessiland suljetaan pois, mutta en ole varma kuinka lähellä olemme", hän sanoi.

Monet tutkijat odottavat, että suurin vaikeus tulee olemaan silloittava näennäisesti harmitonta kuilua kahden erilaisen keskimääräisen tapauksen monimutkaisuuden mallin välillä. Kryptografit tutkivat yleensä keskimääräisiä tapausalgoritmeja, jotka tekevät virheitä molempiin suuntiin ja merkitsevät toisinaan satunnaisia ​​merkkijonoja näennäissatunnaisiksi ja päinvastoin. Hiraharan pahimmasta tapauksesta keskimääräiseen tapaukseen liittyvät vähennykset puolestaan ​​toimivat keskimääräisten tapausten algoritmeille, jotka tekevät vain ensimmäisen tyyppisen virheen. Tämän kaltaiset hienovaraiset erot voivat muuttaa monimutkaisuusteorian maailmaa. Mutta tästä ja monista muista esteistä huolimatta Allender ei voi muuta kuin kuulostaa vartioidulta optimismalta.

"Yritän olla antamatta itseäni olla liian uskovainen, koska meillä on melko vakiintunut kokemus siitä, että mikään ei toimi", hän sanoi. "Mutta näemme paljon todella jännittävää kehitystä - tapoja voittaa esteiltä näyttäneet asiat."

Jos tutkijat ovat oppineet ponnisteluistaan ​​vastatakseen P vs. NP -kysymykseen – tai edes vain ymmärtääkseen sen – se on, että monimutkaisuusteoria on itsessään monimutkainen. Mutta juuri tämä haaste tekee tehtävästä niin palkitsevan.

"Se on todella hienoa, että se on niin vaikeaa", Carmosino sanoi. "Minulle ei tule koskaan tylsää."

Toimittajan huomautus: Scott Aaronson on jäsen Quanta-lehti'S neuvottelukunta.