» »

Problem P ≠ NP za zdaj ostaja nerešen

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, Yang-Millsova teorija in Poincaréjeva domneva. Od teh čaka na rešitev še prvih šest, medtem ko je zadnjega rešil ekstravagantni ruski matematik Grigorij Pereljman. Ali je P enako NP poenostavljeno povedano vprašuje, ali lahko vsak problem, katerega pravilno rešitev lahko preverimo v polinomskem času, tudi rešimo enako hitro. (Primeri takih problemov so potujoči krošnjar in barvanje grafov.) V matematiki prevladuje mnenje, da to ne drži, a dokaza še ni. Eno izmed področij, ki uporablja prav to vejo matematike, je kriptografija, saj današnji šifrirni algoritmi implicitno privzemajo, da v polinomskem času ni mogoče rešiti nekaterih problemov. Če bi se izkazalo nasprotno, bi bil tu hud udarec za varnost šifriranja, medtem ko bi z dokazom laže spali.

Z objavo novice o omenjenem dosežku smo nekoliko počakali, da se je začetna vznesenost polegla in da so si dokaz ogledali ljudje po vsem svetu. Objava je bila v nasprotju z utečenimi smernicami v matematičnem svetu, saj avtor članek poslal neposredno na internet, ne da bi ga poprej pokazal kolegom (peer review). To samo po sebi seveda ne pomeni nič. V starih časih bi čakali nekaj mesecev, da bi se matematiki po svetu prebili skozi članek, a medmrežje je v 21. stoletju te postopke precej pospešilo in tudi poostrilo. Klasični pregled bi se osredotočil na idejo dokaza. Ključna bi bila njena pravilnost in možnost luknje in pomanjkljivosti v realizaciji popraviti.

Na internetu je vse skupaj mnogo ostreje in v le nekaj dneh so matematiki z vsega sveta preštudirali dokaz ter našteli vse najdene pomanjkljivosti. Deolalikar je že dejal, da bo ta konec tedna objavil popravljeno verzijo, in poudaril, da je že prej povedal, da je trenutna verzija delovna. Usoda tega dokaza ostaja nejasna, a na obzorju se rišejo temni oblaki. Toda spomnimo se Wilesovega dokaza Fermatovega izreka, ki je bil objavljen junija 1993. Kasneje se je pokazalo, da ima resne luknje, a se Wiles ni vdal in je septembra prihodnje leto vsem pričakovanjem navkljub objavil popravljeno verzijo, ki je prestala rigorozen pregled.

25 komentarjev

FireSnake ::

Potujoči krošnjar bo pa kar trgovski potnik (problem trgovskega potnika ... sem reševal na različne načine, na koncu še z dinamičnim programiranjem).

Sicer zanimiva novica, a nisem povsem prepričan, da jo je mladež sposobna razumet. Jaz imam za sabo veliko matematike, pa mi marsikaj uide, o nekaterih stvareh se mi pa sploh sanja ne.
" In The Sound Of Silence Time Is Standing Still" " You Have To Learn To Crawl Before You Learn To Walk"

Zgodovina sprememb…

  • spremenilo: FireSnake ()

HairyFotr ::

Potujoči krošnjar je prvi slo-techizem, ki mi je res všeč.

Sicer pa, go Vinay!

jeryslo ::

Mogoče bi pa morali poskusiti narediti nedeterministični Turingov stroj s takoimenovano "čarobno palico";)

sandmat ::

jeryslo je izjavil:

Mogoče bi pa morali poskusiti narediti nedeterministični Turingov stroj s takoimenovano "čarobno palico";)


mogoče bi clo dobili nepovratna sredstva od EU! :)

benji ::

Vsaka čast matematikom,ampak to novico razumem toliko kot matematiki razumejo spolni odnos :)) Video pa je čisti dokaz matematičnega humorja ali karkoli že je to :D

Zgodovina sprememb…

  • spremenilo: benji ()

filip007 ::

Saj bo pa internet hitreje rešil, če so mu dali vse napake, flike noter in je pol manj dela, miljon pa pade :D
PristyTools.com

wooted ::

napake znajo popravlat, sami pa nebi rešil? o.O

Blazz ::

jesus, ker bedn youtube video....

psihoxxx ::

wooted... ja nekak je lažje najdit eno napako v rešitvi kot pa rešitev ki odpravi vse napake in poleg tega mogoče sploh ne obstaja ;)

sicer pa way to go :) je pa res da folk ki ni z fmf / fri ne ve kaj točn gor piše in bi bila mogoče mal bolj laična razlaga na mestu (v osnovi se gre za to v kakšnem času je kakšen problem rešljiv ter če je to še nek 'realen' čas za rešitev - če trdim da lahko nekaj rešim samo dajte mi 10000let (rešujem z brute force metodo oz probujem dokler mi ne rata) to ne pomeni veliko, če pa obstaja preslikava s katero ta problem spremenim v problem, ki ga lahko rešim v enem letu (lahko uporabim nek 'pameten' algoritem za reševanje) ...)


filmček je pa res.... ata matematik hčere so ga pa naje*** :)

modicr ::

Živjo!

Če bi Hitler vedel, da NP ni enako P, mogoče ne bi prišlo do druge svetovne vojne ... :)



Lp, R.
(c) nisem patentiran

Zgodovina sprememb…

  • spremenil: modicr ()

norcuron ::

Za TSP (Traveling Salesman Problem) je malo morje rešitev, od Dijkstre do genetskih algoritmov (zanimivo je gledat kako evolucija šiba skozi generacije).

Sam tale potujoči krošnjar pa zmaga.
Great are mysteries of the mind ... or not?

Zgodovina sprememb…

  • spremenil: norcuron ()

rasta ::

Dijkstrov algoritem ni rešitev TSP, ampak najkrajše poti med A in B.

Kar se pa tiče algoritmov hevrističnega iskanja, pa ti v splošnem najdejo suboptimalno rešitev.

modicr ::

Živjo!

Fermat je čečkal bo Diofantovi Aritmetiki - in ni bil edini: http://books.google.com/books?id=yoIhl3...

'May your soul, o Diophantus, rest with Satan 
on account of the difficulty of your other theorems 
and particularly of the present theorem'

Lp, R.
(c) nisem patentiran

Zgodovina sprememb…

  • spremenil: modicr ()

Gandalfar ::

Thomas in i100k100, prepucavajta se naprej v ZS.

norcuron ::

Hypnotic, kako bi lahko genetski algoritem v tem primeru uporabil? Razumem za optimizacijo iskanja recimo gradientov ali kaj podobnega, samo v tem primeru pa si ne znam tega predstavljati - niti teoretično.


Nekaj primerov:
TSP - java applet - lahko spreminjaš nastavitve GA
A fast TSP solver using a genetic algorithm
Genetic Algorithms and the Traveling Salesman Problem
Great are mysteries of the mind ... or not?

MrStein ::

Primeri takih problemov so potujoči krošnjar


OK, čas za preimenovanje v slo-pesnik.com ?

Mislim, če bi radi izrazili svoja čustva je tu podforum Sedem umetnosti
Teštiram če delaž - umlaut dela: ä ?

Thomas ::

Čist tko, kot zanimivost. Tale problem bi rešil, kdor bi za poljubno odprtje MineSweeperja (igrico iz Windows) našel način, kako v polinomskem času ugotoviti, če je pozicija (npr. napol odigrana igra), sploh logično konzistentna.

To najdeš in si dokazal P=NP.

Dokažeš da take metode ni in si okazal P!=NP.
Man muss immer generalisieren - Carl Jacobi

Double_J ::

V knjigi ni imel prostora, a je bil papir predrag?

Najbrž pač ni imel tega dokaza in je kjerkoli že, napesnil en izgovor.
Dve šivanki...

Thomas ::

Predvsem tisti problem ni bil ta problem. Fermat je tukaj rahlo off topic.

Ne pa čisto, navsezadnje ju druži najmanj milijon dolarjev od Clay instituta.

Fermat je verjetno verjel, da ima dokaz. Ker ni tako težko dokazati, da vsota dveh kubov ni kub, razen za 0^3+1^3=1^3 in podobne trivialne primere, kar je Fermat omenil prav v tisto knjigo.

Samo da velja pa to splošno, za vse n nad 2, se je pa malo zaletel. Sicer velja, ampak oreh je bil trd 300 let.

P=NP ali P!=NP je pa mlajši, pomembnejši in morda ravno tako težek problem.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Drugače pa, Fermat je domneval še nekaj drugega, kar se je pa izkazalo za narobe. Namreč, da so vsa števila oblike 2^(2^N)+1, ki so potem dobila po njem ime, praštevila.

Rekel je, da za to nima dokaza, samo občutek. Euler je dokazal, da ga je občutek varal. Skoraj 300 let nazaj že.

Človek je imel domneve, ki so zaznamovale zgodovino.
Man muss immer generalisieren - Carl Jacobi

gzibret ::

Klik - od tu naprej brisanih nadaljnjih 12 postov (sklicevanje na lastno avtoriteto, obračunavanje na osebnem nivoju, offtopic posti).

edit - update - pobrisan tudi izvor silnih kreganj (ki je tudi offtopic)....
Vse je za neki dobr!

Zgodovina sprememb…

  • spremenilo: gzibret ()

Thomas ::

Da se tema ne zatre ...

a propos, MineSweeper varianta P?=NP pravi, da se vsak algoritem da enolično izraziti z neko konsistentno slikico "napol rešenega" MSMS-ja (MicroSoftMineSweeper). To ni nekaj kar bi bilo šele treba dokazati, to je tako.

Ne ve se samo, če je mogoče v polinomskem (namesto eksponentnem) času dokazati, da je ali ni, "napol rešena" pozicija protislovna! Če bi to lahko, bi vsak eksponentni algoritem lahko bistveno pospešili.

Samo skoraj nihče ne verjame, da ni tale consistency probing ekstremno zaguljen. Čeprav je na prvi pogled to "sprehod skozi park", poskusite narediti program, ki bo za vsako slikco povedal, če je legalna ali ni. Če sta recimo 1 in 8 sosednja kvadrata, že ni legalna. tudi če vsebuje vrstico/stolpec 141 - ni legalna.
Man muss immer generalisieren - Carl Jacobi

gzibret ::

Nekaj ne razumem. Napol rešena pozicija MSMS-ja ni nikoli protislovna (saj ima eno in samo eno točno določeno rešitev). Prej bi rekel, da je rešitev napol rešenega MSMS-ja včasih nedoločena. Problem je le v tem, da je treba včasih malo gamblat, da prideš do rešitve.

Samo še vedno ne vem, kje ima (ne)polinomsko število operacij, ki vodi do rešitve, tukaj prste zraven.
Vse je za neki dobr!

whatever ::

Jaz tudi ne zastopim analogije z minesweeperjem. Pa me zanima več. Kaj točno, je treba dokazat, če se te analogije poslužimo?

pecorin ::

o tem so ze dosti pisali. npr.:
http://www.claymath.org/Popular_Lecture...


Vredno ogleda ...

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

Problem P ≠ NP za zdaj ostaja nerešen

Oddelek: Novice / Znanost in tehnologija
255754 (2590) pecorin
»

Ruski matematični čarovnik zavrnil nagrado

Oddelek: Novice / Znanost in tehnologija
488091 (4210) donfilipo
»

Bo matematični čarovnik iz Rusije sprejel milijon dolarjev nagrade? (strani: 1 2 )

Oddelek: Novice / Znanost in tehnologija
578965 (5346) Bor H
»

kam naprej za prfoksa matematke na srednji šoli

Oddelek: Šola
342792 (2205) BluPhenix
»

Cantor, Russell ... Teorija množic. (strani: 1 2 3 )

Oddelek: Znanost in tehnologija
1434583 (3064) Odin

Več podobnih tem