HP Forsker hævder Compsci Complexity Conundrum

Mens Hewlett-Packard ruller fra Udfaldet af sin CEO Mark Hurd går ned, virksomheden kan baske i ære af mindst en potentielt positiv gennemførelse: En HP-forsker har tilbudt det, han siger, er en løsning på et af de sværeste problemer inden for datalogi.

HP Labs hovedforsker Vinay Deolalikar har skrevet, hvad han hævder er en løsning på, hvad der er kendt som P versus NP-problemet.

Så intractable er dette problem, som Clay Mathematics Institute har lovet at tildele den person, der løser det, USA $ 1 mio. Det er en af ​​kun syv problemer, samlet kendt som Millenniumprisproblemerne, instituttet har tilbudt denne gevinst for. En af de syv, Poincaré-formodningen, blev officielt løst i 2006.

Det er uklart, om Deolalikar vil få kontanter, da Clay ikke har sagt, at det betragter problemet løst.

Dette problem, "en af de udestående problemer inden for datalogi "involverer" at bestemme, om der findes spørgsmål, hvis svar hurtigt kan kontrolleres, men som kræver en umulig lang tid at løse ved enhver direkte procedure, "forklarer en institutside. I problemet står P for polynomisk tid, og NP står for nondeterministisk polynomitid.

"Jeg er glad for at kunne meddele et bevis på, at P ikke er lig med NP", meddelte Deolalikar i en e-mail til en gruppe matematikprofessorer, som siden blev udsendt på søndag af Greg Baker, en lektor ved British Columbia Simon Fraser University.

I en nøddeskal kan dette betyde, at visse problemer kun kan løses ved hjælp af brute force search, hvis der findes løsninger på alle.

"Beviset krævede sammenlægning af principper fra flere områder inden for matematik. Den store indsats i at opbygge dette bevis var at afdække en kæde af konceptuelle forbindelser mellem forskellige felter og se dem gennem en fælles linse," skrev Deolalikar.

Naturligvis taler de, der er dygtige til problemet, med at forkynde, at Deolalikar har løst problemet, i betragtning af mængden af ​​kontrol, der skal gøres. Og mens de roser Deolalikar for sin grundige tilgang, som adskiller sig fra de mere tilfældige gæt, der normalt præsenteres, har ingen endelig påstået, at han har sprængt problemet.

"Det ser ud til at introducere nogle tankevækkende nye ideer, især en sammenhæng mellem statistisk fysik og den første ordens logiske karakterisering af NP, "skrev Scott Aaronson, assistent professor i elektroteknik og datalogi ved Massachusetts Institute of Technology i en ikke-kommende blogindgang.

" Jeg ved ikke hvad at tænke lige nu, men jeg er bestemt håb, "skrev Dick Lipton, professor i computervidenskab ved Georgia Institute of Technology.

Joab Jackson dækker firmware og generel teknologi, der bryder nyheder til IDG News Service. Følg Joab på Twitter på @Joab_Jackson. Joabs e-mail-adresse er [email protected]