Zagonetka P naspram NP: Hoće li umjetna inteligencija razriješiti matematički Sveti Gral?

Problem P naspram NP promatra se iz dviju perspektiva: kao formalna, matematički definirana pretpostavka koja nosi status jednog od Clay Millennium Problemsa, i kao intuitivnija ideja da je sve što se može učinkovito provjeriti također učinkovito izračunljivo, s posljedicama koje iz toga proizlaze za naše računalne sposobnosti. U prošlosti sam opsežno pisao o tome kako je umjetna inteligencija utjecala na ovu potonju interpretaciju. Primjerice, AI i drugi napreci u računalstvu doveli su nas do svojevrsnog “Optilanda”, gdje uživamo u većini pozitivnih implikacija pretpostavke P=NP, dok naši kriptografski sustavi ostaju neprobojni. Međutim, s obzirom na nedavne iskorake u pogledu dokaza generiranih i podržanih umjetnom inteligencijom, postavlja se pitanje hoće li AI promijeniti naše razumijevanje formalne matematičke tvrdnje? Je li na pomolu dokaz P ≠ NP generiran umjetnom inteligencijom?

Odgovor je, jasno i nedvosmisleno: Ne. Osobno ne vjerujem da ćemo u mom životnom vijeku svjedočiti dokazu problema P naspram NP, bio on postignut od strane čovjeka, stroja, ili njihove zajedničke suradnje.

Iako je opovrgavanje problema Erdősove jedinice udaljenosti impresivno postignuće umjetne inteligencije, važno je imati na umu da na svaki matematički dokaz postignut AI-jem, postoji stotine problema koje smo pokušali riješiti uz pomoć AI-ja bez značajnijeg napretka. Također, postoji ogroman jaz između kombinatornih pretpostavki poput Erdősovih i problema poput onih iz Clay Millennium zbirke. Umjetna inteligencija će se nastaviti razvijati, ali postoje granice.

Ljudi, osobito oni izvan područja računalne složenosti, često ne shvaćaju koliko je ovaj matematički izazov težak. Polinomijalni algoritmi mogu djelovati na neobične i misteriozne načine. Oni ne moraju nužno poštivati semantiku NP-pretraživačkog problema, niti obavljati bilo kakvo pretraživanje. Moj kolega Bill jednom mi je dao sljedeći “algoritam” za pronalazak klika: “Uzmite svojstvene vrijednosti matrice susjedstva. Tko će ga znati, možda ako postoje dva prosta broja p i q takva da se p-ta i q-ta svojstvena vrijednost razlikuju za više od 1/k, graf ima k-klik.” Naravno, ovo ne funkcionira. Ali da biste dokazali P ≠ NP, potrebno je dokazati ne samo da ovaj algoritam ne funkcionira, već ni bilo koji od beskonačno mnogo drugih potencijalnih algoritama za rješavanje NP-potpunih problema.

Jednostavno ne znamo za učinkovit način upravljanja općim polinomijalnim algoritmima osim njihovom simulacijom. Relativizacijom je dokazano da simulacija i dijagonalizacija neće riješiti problem P naspram NP. Ostali pokušaji razumijevanja polinomijalnog vremena, poput složenosti sklopova, složenosti dokaza i algebarske geometrije, zapeli su daleko ispod pune snage polinomijalnog vremena. Trenutačno nemamo niti održiv pristup rješavanju problema P naspram NP.

Ne gubite vrijeme pokušavajući formalni pristup putem sustava Lean. (Ovo se odnosi na tebe, Dmitry Khanukov.) Računalna složenost je tehnički vrlo neuredna za formuliranje. Ne mogu natjerati AI da mi pruži potpun, Lean-verificiran dokaz nečega trivijalnog poput svojstva da je P zatvoren pod komplementom, a kamoli PCP teorema. Ako netko ili nešto i dođe do dokaza P ≠ NP, to će biti slijedeći ispravan intuitivni pristup, a ne isključivo formalistički.

Za početak, bavite se nečim jednostavnijim, poput dokazivanja da je BPP u subeksponencijalnom vremenu, ili da SAT nema kvadratne algoritme. Ni tamo nećete uspjeti, iako bi ova pitanja trebala biti galaktički jednostavnija od P ≠ NP.