HP Researcher twierdzi, że Crack Compsci Complexity Conundrum

Podczas gdy Hewlett-Packard kołuje od spadki prezesa Marka Hurda ustąpiły, firma może się pochwalić co najmniej jednym potencjalnie pozytywnym osiągnięciem: badacz HP zaoferował to, co mówi, jest rozwiązaniem jednego z najtrudniejszych problemów w informatyce.

Główny naukowiec HP Labs Vinay Deolalikar opublikował to, co twierdzi, jest rozwiązaniem problemu, który jest powszechnie znany jako problem P versus NP.

Tak trudny jest ten problem, że Instytut Matematyki Clay przyrzekł nagrodzić osobę, która rozwiązuje to US 1 milion USD. Jest to jeden z zaledwie siedmiu problemów, zwanych łącznie problemami z nagrodami milenijnymi, instytut zaoferował tę nagrodę. Jedno z siedmiu przypuszczeń Poincarego zostało oficjalnie rozwiązane w 2006 roku.

Nie jest jasne, czy Deolalikar dostanie pieniądze, ponieważ Clay nie powiedział, że uważa, że ​​problem został rozwiązany.

Ten problem, "jeden z zaległe problemy z informatyką "wiążą się" z określeniem, czy istnieją pytania, których odpowiedź można szybko sprawdzić, ale które wymagają niemożliwie długiego czasu na rozwiązanie za pomocą dowolnej bezpośredniej procedury "- wyjaśnia strona Instytutu. W problemie P oznacza czas wielomianowy, a NP oznacza niedeterministyczny czas wielomianu.

"Z przyjemnością ogłaszam dowód, że P nie jest równy NP," Deolalikar ogłosił w e-mailu do grupy profesorów matematyki, który został wysłany w niedzielę przez Grega Bakera, starszego wykładowcę na Kolumbii Brytyjskiej Uniwersytetu Simona Frasera.

W dużym skrócie, może to oznaczać, że pewne problemy można rozwiązać tylko poprzez brutalne poszukiwania siły, jeśli można znaleźć rozwiązania na all.

"Dowód wymagał złożenia w całość zasad z wielu dziedzin w matematyce.Jednym z głównych wysiłków włożony w ten dowód było odkrycie łańcucha pojęciowych powiązań między różnymi polami i oglądanie ich przez wspólną soczewkę," napisał Deolalikar.

Naturalnie, osoby znające się na tym problemie wahają się ogłosić, że Deolalikar rozwiązał problem, biorąc pod uwagę liczbę kontroli, które należałoby wykonać. I chwaląc Deolalikara za jego dokładne podejście, które różni się od bardziej przypadkowych domysłów, które są zwykle prezentowane, nikt nie stwierdził ostatecznie, że złamał problem.

"Wydaje się, że wprowadzają pewne prowokujące do myślenia nowe pomysły, szczególnie związek między fizyką statystyczną a logiką pierwszego stopnia w NP - napisał Scott Aaronson, adiunkt inżynierii elektrycznej i informatyki w Massachusetts Institute of Technology, w niezobowiązującym wpisie na blogu.

"Nie wiem co myśleć teraz, ale jestem z pewnością pełen nadziei "- napisał Dick Lipton, profesor informatyki w Georgia Institute of Technology.

Joab Jackson opisuje oprogramowanie dla przedsiębiorstw i ogólne nowości technologiczne dla Serwisu IDG News. Śledź Joaba na Twitterze na @Joab_Jackson. Adres e-mail Joaba to [email protected]