Slo-Tech - Ruski matematik Vladimir Romanov je naslednji v vrsti znanstvenikov, ki predstavljajo svoj poizkus dokaza milenijskega matematičnega problema, ali je P enako NP. Lani je k temu resno pristopil Vinay Deolalikar, a je bil njegov poizkus neuspešen. Problem P = NP vprašuje, ali lahko vsak problem z v polinomskem času preverljivo rešitvijo enako hitro tudi rešimo. Zdi se, da to ne drži, a v matematiki slutnje in domneve bolj malo štejejo.
Spletni komentarji za zdaj kažejo, da bo ta poizkus dokaza doletela enaka usoda kot predhodne. Že v nekaj dneh bo jasno, ali ima za dokaz resne možnosti, da bi obveljal.
Če bi jaz koval dokaz, da P!=NP sevedA, potem bi ... imam ene ideje, kako bi to šlo. Samo ne bom pravil, če ne dokažem. Dokazal pa ne bom, ker niti ne dokazujem.
Posledice odkritja P == NP bi bile v resnici veliko milejše, kot predvidevajo nekateri (slashdot: AES razbit, nebo pada!!!1). Tudi enkripcijski sistemu, ki temeljijo na NP-popolnosti, bi lahko samo podaljšali enkripcijske ključe za red velikosti, in bi bili še kakšno desetletje nepremagljivi tudi za napade, ki se poslužujejo na P==NP temelječih algoritmov. Do takrat pa bo vse, kar danes vemo o računalniški znanosti antična zgodovina.
Brca (najverjetneje) v temo: Kaj pa quantum-based algoritmi?
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|
Brca (najverjetneje) v temo: Kaj pa quantum-based algoritmi?
Wikipedia pravi da ti to prav nič ne pomaga pri reševanju NP-polnih problemov. Moje mnenje je, da pač s kvantnim računalnikom (če to ne bi bil bolj ko ne PoC) lahko počneš stvari izredno hitro - saj vse "staličiš" v en qubit in potem z njim čaraš. Ampak problem je pa na koncu: kako prebrati rezultat, ker z meritvijo vse uničiš. Dokaz, da je BQP večji kot BPP je pomoje ravno Shorov algoritem s katerim se da število faktorizirati v polinomskem času.
Meni se zdi tudi bolj intuitivno, da P != NP. Argument za to je nekako, da obstaja kar nekaj praktično uporabnih NP-polnih problemov za katere je že sigurno kdo razmišljal o njihovi optimizaciji (tako da bi jih rešil točno v polinomskem času), ampak nobeden še ni prišel z rešitvijo in tako ni še nihče dokazal P = NP. Vse skupaj jasno ni dokaz (da nekaj ni bilo dokazano še ne pomeni, da mora veljati nasprotno), le za občutek...
Mogoče bo pa zdaj dokazano da P = NP. Pri tem članku me je malo strah, da bo nekje iz ozadja skočila ena 2^n, ki je avtor ni upošteval in bo vse šlo k vragu.
fiction: Ja, točno to sem tudi sam mislil. Da bi morda lahko z kvantno mehaniko dokazali, da P != NP. Malo sem brskal po scholar.google in je tega materiala res veliko, vendar nisem našel nič konkretnega. Zato sem pa tukaj vprašal za "drugo" mnenje.
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|
Če bi jaz koval dokaz, da P!=NP sevedA, potem bi ... imam ene ideje, kako bi to šlo. Samo ne bom pravil, če ne dokažem. Dokazal pa ne bom, ker niti ne dokazujem.
Lisica bi tudi jedla grozdje, če ne bi bilo ... kislo.
