P = NP gåten løst? Indisk forsker foreslår bevis ved Bipin Shah

New Delhi: En forsker ved navn Vinay Deolalikar på Hewlett-Packard (HP) Labs i California har kommet opp med et mulig bevis for den berømte P = NP problem i matematikk. Bragden kan gjøre ham tjene $ 1 million (Rs 4,6 crore.) For å løse en av de syv Clay Mathematics Institute Millennium problemer, melder Samanth Subramanian av Mint.

I en e-post til sine forskerkolleger Deolalikar skrev at han hadde gjort flere mislykkede forsøk på å prøve andre kombinasjoner av ideer før han begynte dette arbeidet.

Før du godtar ved den matematiske samfunnet, må papiret til å bli publisert i en større referee journal. Det må bli akseptert av den matematiske fellesskapet innen to år etter publikasjonen for Deolalikar å samle sine Clay premie.

Ifølge Stephen Cook, som har skrevet den offisielle beskrivelsen av P = NP problem for Clay Institute, Deolalikar har gjort en alvorlig hevder å ha løst P vs NP.

P = NP problemet er en meta-problem med særlig relevans for informatikk. "P" i denne ligning refererer til en klasse av problemer; hvis tiden som trengs for å løse et problem ikke vokse eksponensielt med data som er gitt, er problemet en type-P problem. En NP problem, derimot, er en som du kan sjekke om en foreslått løsning er virkelig en løsning i rimelig tid.

P = NP problem spørsmål hvorvidt en NP problemet er det samme som en P problem. Med andre ord, hvis et problem har løsninger som kan verifiseres i polynomisk tid, så kan problemet også løses i polynomisk tid?

Helt siden problemet ble oppgitt, uavhengig av Cook og Leonid Levin i 1971, matematikere trodd at P ikke gjør det, faktisk, lik NP - men ingen akseptable bevis for at ulikhet er funnet

Deolalikar bevis, som søker å etablere at P er ikke lik NP har, i bare noen få dager, kvernet opp betydelig spenning innenfor det matematiske samfunnet.

Deolalikar bevis vil være den andre av de syv Millennium problemer å ha falt i løpet av de siste årene, hvis det er publisert og finner den "generell aksept" at Clay