HP-ova istraživačica tvrdi da je stvorila kompliciranost kompleksnosti

Dok Hewlett-Packard tvrtka Fallout odlazi iz slavlja barem jednog potencijalno pozitivnog postignuća: HP-ov istraživač ponudio je ono što kaže kako je rješenje jednog od najtežih problema računalne znanosti.

Glavni istraživač tvrtke HP Labs Vinay Deolalikar objavio je ono što tvrdi da je rješenje onoga što je poznato kao problem P vs. NP.

Tako je nemaran problem koji je Clay Mathematics Institute obećao dodijeliti osobu koja to rješava SAD 1 milijun dolara. To je jedan od samo sedam problema, zajednički poznat kao Milenijska nagrada Problemi, institut je ponudio ovu nagrada za. Jedan od sedam, nagađanja o Poincaréu, službeno je riješen 2006. godine.

Još je nejasno ako Deolalikar dobije novčanu naknadu, budući da Clay nije rekao da smatra da je problem riješen.

Ovaj problem " postojeći problemi u računalnoj znanosti "uključuje" određivanje postoje li pitanja koja se mogu brzo provjeriti, ali za koje je potrebno nevjerojatno dugo rješavanje bilo kojim izravnim postupkom ", objašnjava Institut. U problemu, P je polinomna vremena, a NP označava neodređeno polinomno vrijeme.

"Zadovoljstvo mi je objaviti dokaz da P nije jednak NP", rekao je Deolalikar u e-mail grupi profesora matematike, koji je u nedjelju objavio Greg Baker, viši predavač na Sveučilištu British Columbia Simon Fraser.

Ukratko, to može značiti da se određeni problemi mogu riješiti samo pretraživanjem sive sile, ako se rješenja mogu naći na sve.

"Dokaz je zahtijevao povezivanje principa s više područja unutar matematike, a glavni napor u izradi ovog dokaza bio je otkrivanje lanca konceptualnih veza između različitih područja i njihovo gledanje kroz zajedničku leću", napisao je Deolalikar.

Naravno, oni koji su upoznati s problemom oklijevaju navesti da je Deolalikar riješio problem, s obzirom na količinu provjere koja bi trebala biti učinjena. I dok hvale Deolalikara zbog njegovog temeljitog pristupa, onaj koji se razlikuje od slučajnijih pretpostavki koje se obično prikazuju, nitko nije definitivno tvrdio da je razbio problem. "Čini se da uvodi neke nove ideje koje izazivaju misli, osobito veza između statističke fizike i logičke karakterizacije prvog reda NP-a ", napisao je Scott Aaronson, pomoćnik profesora elektrotehnike i računalnih znanosti na Massachusetts Institute of Technology, u nezavisnom blogu.

" Ne znam što da razmišljam upravo sada, ali zasigurno se nadam ", napisao je Dick Lipton, profesor računalne znanosti na Tehnološkom institutu Georgia.

Joab Jackson pokriva softverske programe i opće tehnološke vijesti za

IDG News Service. Slijedite Joab na cvrkut na @Joab_Jackson. Joabova adresa e-pošte je [email protected]