Slo-Tech - Eden izmed najprivlačnejših matematičnih problemov, katerega rešitev bi pomembno vplivala na tudi na računalništvo, je vprašanje ali je P enako NP. Gre za enega izmed sedmih tako imenovanih tisočletnih problemov v matematiki, z rešitvijo katerega lahko od Clay Mathematics Instituta dobimo milijon dolarjev nagrade (kar je nekoliko več od Nobelove nagrade). Doslej je bil rešen samo eden izmed sedmerice problemov. Problem P proti NP sprašuje, ali za vsak problem, katerega rešitev lahko preverimo v polinomskem času, v polinomskem času tudi rešimo. O tovrstnih vprašanjih so se pogovarjali že Nash, Gödel in von Neumann, rigorozno formulacijo pa je leta 1971 postavil Stephen Cook.

Trenutno prevladujoče mnenje v znanosti je, da velja P ≠ NP...

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...

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.

Romanov je objavil članek z naslovom Non-Orthodox Combinatorial Models Based on Discordant Structures, v katerem predstavlja algoritem za rešitev problema 3-sat v polinomskem času. Ker je 3-sat NP-poln problem, bi bil to že dokaz, da velja P = NP. V...

Slo-Tech - Relativno neznani matematik Vinay Deolalikar, ki je zaposlen v Hewlett-Packardu, je prejšnji konec tedna osupnil svet s povsem resno objavo, da je dokazal milenijski matematični problem, da P ni NP. Domnevni dokaz obsega 102 strani in ni le potegavščina, marveč zaresen poizkus dokaza tega problema. Žal po nekaj dneh pregledovanja internetne skupnosti lahko skoraj gotovo zaključimo, da neuspešen.

Clay Mathematics Institute of Cambridge iz Massachusettsa je na prelomu tisočletja razpisal nagrado milijon dolarjev za rešitev vsakega izmed sedmih največjih nerešenih (poimenovanih milenijski) problemov v matematiki. Ti so Swinnerton-Dyerjeva domneva, Hodgeova domneva, Navier-Stokesove enačbe, problem P = NP, Riemannova hipoteza,

The New York Times - Clay Mathematics Institute of Cambridge iz Massachusettsa je na prelomu tisočletja razpisal nagrado milijon dolarjev za rešitev vsakega izmed sedmih največjih nerešenih (poimenovanih milenijski) problemov v matematiki. Ti so Swinnerton-Dyerjeva domneva, Hodgeova domneva, Navier-Stokesove enačbe, problem P = NP, Riemannova hipoteza, Yang-Millsova teorija in Poincaréjeva domneva. Slednjo je leta 1904 postavil francoski matematik Henri Poincaré in predstavlja topološki problem. V topologiji velja, da je 2-sfera enostavno povezano območje, kar pomeni, da je povezano s potmi in da lahko...