Prijavi se z GoogleID

» »

Januarski poizkus dokaza problema P = NP neuspešen

Januarski poizkus dokaza problema P = NP neuspešen

Slashdot - Propadel je še en poizkus dokaza slavnega problema P = NP?, za katerega je razpisana nagrada milijon dolarjev in ki vprašuje, ali so vsi problemi, za katere je moč dane rešitve preveriti v polinomskem času, tudi rešljivi enako hitro. Ruski matematik Vladimir Romanov je svoj dokaz objavil januarja letos in na prvi pogled je kazalo, da utegne biti korekten. Izkazalo se je, da milijona dolarjev še ne bo dobil.

Napako je v dokazu po enomesečnem seciranju priznal kar sam avtor, a puške še ni vrgel v koruzo. Zapisal je namreč tudi, da dokaz potrebuje dopolnilo in namignil, da ga bo predložil. Za zdaj pa dodajamo njegov dokaz v dolgo vrsto neuspelih poizkusov, ki smo jih zadnjih 30 let videli že nekaj.

Problem si lahko v tipični slovenski maniri predstavljamo takole. Na banket želimo povabiti 100 gostov, ki jih lahko izberemo iz na primer množice 1000 ljudi. Vsak izmed teh je navedel pogoje, ob katerih se bo banketa udeležil. Ti pogoji so obvezna prisotnost ali odsotnost nekaterih oseb (z nekaterimi so dobri kolegi, z drugimi so sprti) na pogostitvi. Za vsako množico ljudi lahko hitro preverimo, ali ustreza vsem pogojem, medtem ko je poiskati tako množico, ki bo pogojem ustrezala, bistveno teže.

Dokaz, najsi bo odgovor da ali ne, bi imel pomembne posledice za računalništvo. Najočitnejši primer je šifriranje, ki se trenutno opira na nedokazano predpostavko, da P ni enako NP. Če bi uspeli dokazati, da to ne velja, bi to pomenilo, da so šifrirni algoritmi bistveno manj varni, kot smo mislili.

6 komentarjev

KoMar- ::

Rešitev je preprosta: ne ponujajmo tako velike nagrade, da se nikomur ne bo dalo ubadat s tem in ostanemo varni.

(To je tudi en vidik, ne?)

Zgodovina sprememb…

  • spremenil: KoMar- ()

Terman ::

Nekateri se bodo ubadali s tem iz lastnega veselja. Če k temu prištejemo še neskončno opic s pisalnimi stroji teorijo...

eudaemon ::

Dokaz, najsi bo odgovor da ali ne, bi imel pomembne posledice za računalništvo.

V pozitivnem primeru, če je P = NP, bi bile posledice izjemne: v kriptografiji bi se sicer morali vrniti k uporabi one-time padov (ali morda h kaki meni neznani eksotiki), kar se pa tiče drugih področij... pa je le za odtenek pretirano reči, da bi postali praktično bogovi.

Polinomski algoritem za NP-polne probleme bi prinesel preprosto avtomatizacijo celotne matematike, učinkovito, splošno iskanje vzorcev v ogromnih količinah podatkov, kar bi povsem približalo realnosti tudi 'pravo' umetno inteligenco. Hitro sestavljanje urnikov za pristajanje letal in podobne aplikacije, ki se običajno omenjajo, so samo drobtinice. Se pa tega dejstva zaveda le peščica - zaradi česar ga tudi omenjam tule...

Najočitnejši primer je šifriranje, ki se trenutno opira na nedokazano predpostavko, da P ni enako NP.

Dejansko kriptografija počiva na močnejših predpostavkah kot je P != NP, ker je na žalost nihče še ne zna bazirati na NP-polnih problemih. Dokaz, da je P != NP torej ne bi bil dovolj za zagotovitev varnosti današnjih kriptografskih sistemov (z izjemo one-time pada).

Mimogrede, težavnost faktorizacije na kateri je osnovan RSA ni enaka težavnosti NP-polnih problemov - splošno prepričanje v krogih teoretičnega računalništva je, da je faktorizacija eden izmed tistih problemov, ki ležijo med NP-polnimi/težkimi in P problemi.

Če bi uspeli dokazati, da to ne velja, bi to pomenilo, da so šifrirni algoritmi bistveno manj varni, kot smo mislili.

RSA razbijejo že kvantni računalniki, ki sicer niso sposobni učinkovitega reševanja NP-polnih problemov - pri čemer se ob vsem tem opiramo na (zelo trdno) hipotezo P != NP. V nasprotnem primeru pa RSA odpihne že na klasičnih računalnikih, kakor tudi vse druge kriptografske protokole (z že omenjeno izjemo). Torej, ne le da bi bili bistveno manj varni, če velja P = NP, bili bi povsem ne-varni - in hkrati bogovi. :)

V zvezi s P vs. NP dokazi bi še omenil, da bo preteklo še mnogo vode dokler bo sploh mogoča neka realistična možnost za uspešen napad na dokaz. Doslej se je pojavilo kup dokazov raznih crackpotov, peščica resnejših, vendar daleč od pravilnosti in takšno stanje bomo skoraj zagotovo spremljali še mnogo let.

(Nekaj o tem pove tudi nedavna izjava Scotta Aaronsona (theoretical CS wiz-kid), da je pripravljen nagraditi Deolalikarjev P != NP dokaz, v primeru, da bi se izkazal za pravilnega, z 200k$ iz lastnega žepa. Pričakovano se je izkazal za napačnega, pove pa takšna izjava nekaj o tem, kako daleč naj bi po pričakovanjih stroke še bili od pravega dokaza.)
"Do not propose solutions until the problem has been discussed as thoroughly
as possible without suggesting any." R.F.Maier

Zgodovina sprememb…

  • spremenilo: eudaemon ()

Thomas ::

No, vseeno jaz ne bil vzel vsega upanja ambicioznežem.

Imamo dve možnosti, da P!=NP (IMHO verjetnejša) ali da P=NP (IMHO manj verjetna).

Če želi kdo dokazati bodisi eno, bodisi drugo varianto, naj dokaže samo to, da je konzistenca poljubne MineSweeper pozicije nedokazljiva ali dokazljiva v polinomskem času.

S tem bo dokazal vse, kar je za to potrebno. Ne rečem, da je lahko, vendar ni tako divje, kot v začetku zgleda.
Man muss immer generalisieren - Carl Jacobi

eudaemon ::

Obstaja še tretja možnost: da je P=NP? vpr. neodvisno od ZFC aksiomov tako kot na primer hipoteza kontinuuma. Čeprav za razliko od slednje to ne pomeni, da je mogoče kar po občutku privzeti eno izmed pozicij (v bistvu niti pri CH to morda ne velja) - še vedno bi veljalo P!=NP ali obratno, le dokazati nam ne bo uspelo tega dokler ne poiščemo nekega drugega sprejemljivega aksiomatskega sistema.

Poleg Minesweeperja obstaja še nekaj tisoč poznanih NP-polnih problemov za katere velja enako. Komur uspe poiskati polinomski algoritem za kateregakoli izmed njih, bo pokazal P=NP, in obratno, če uspe dokazati, da takšen algoritem ne obstaja. Glede na dolgo zgodovino neuspelih poskusov in ogromno truda, ki je bil vložen v to, gre očitno za vse prej kot lahek podvig in dvomim, da ga konkretnost Minesweeperja kaj dosti olajša.

Omejitve današnjih tehnik dokazovanja tudi nakazujejo, da bo potrebno najti nek povsem nov pristop, zaradi česar se v TCS krogih govori, da bi dokaz P!=NP imel 'paradigmatične posledice' za naše razumevanje računanja...

Zanimiva je tudi samo-referencialnost oz. 'metamatematičnost' P=NP? problema: če velja P!=NP, je to dejansko trditev, ki govori o veliki težavnosti svoje lastne dokazljivosti, saj dokazovanje matematičnih teoremov (do neke omejene dolžine) spada med NP-polne probleme. Kako torej dokazati trditev, ki pravi, da jo je zelo težko dokazati (in ki je splošno sprejeta kot resnična)? :)

Skratka, globoko in fascinantno vprašanje, ki ne sedi zastonj na tronu med Milenijskimi problemi, za katerega razrešitev bo morda potrebno počakati kako stoletje ali več, podobno kot pri Fermatu... (če pustimo ob strani singularnost, seveda).
"Do not propose solutions until the problem has been discussed as thoroughly
as possible without suggesting any." R.F.Maier

Thomas ::

v bistvu niti pri CH to morda ne velja


Ne, ne, tam velja. Kakor morda želite, to lahko dobite.

Sicer se strinjam z vsem napisanim.
Man muss immer generalisieren - Carl Jacobi


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Januarski poizkus dokaza problema P = NP neuspešen

Oddelek: Novice / Znanost in tehnologija
63438 (1974) Thomas
»

Predstavljen poizkus dokaza P = NP

Oddelek: Novice / Znanost in tehnologija
135481 (3710) gzibret
»

Problem P ≠ NP za zdaj ostaja nerešen

Oddelek: Novice / Znanost in tehnologija
257451 (4287) pecorin

Več podobnih tem