HP Forscher behauptet, Compsci Complexity Conundrum zu knacken

Während Hewlett-Packard aus Nach dem Rücktritt seines CEO Mark Hurd kann sich das Unternehmen mindestens eine potentiell positive Errungenschaft leisten: Ein HP-Forscher hat angeboten, was er sagt, ist eine Lösung für eines der schwierigsten Probleme der Informatik.

HP Labs Hauptforschungswissenschaftler Vinay Deolalikar hat veröffentlicht, was er behauptet, ist eine Lösung für das, was weithin als das P gegen NP-Problem bekannt ist.

So hartnäckig ist dieses Problem, das Clay Mathematics Institute gelobt hat, die Person, die es uns löst 1 Million Dollar. Es ist eines von nur sieben Problemen, die zusammen als Millennium Prize Probleme bekannt sind, für die das Institut diese Prämie angeboten hat. Eine der sieben, die Poincaré Vermutung, wurde 2006 offiziell gelöst.

Es ist noch unklar, ob Deolalikar das Geld bekommen wird, da Clay nicht gesagt hat, dass es das Problem als gelöst ansieht.

Dieses Problem, "eines von Die offensichtlichen Probleme in der Informatik "beinhalten", ob Fragen existieren, deren Antwort schnell überprüft werden kann, die aber durch ein direktes Verfahren eine unglaublich lange Zeit zu lösen brauchen ", erklärt eine Institutsseite. In dem Problem steht P für die Polynomzeit und NP für die nichtdeterministische Polynomzeit.

"Ich freue mich, einen Beweis anzukündigen, dass P nicht gleich NP ist", kündigte Deolalikar in einer E-Mail an eine Gruppe von Mathematikprofessoren an, die dann am Sonntag von Greg Baker, einem Dozenten an der Simon Fraser Universität in British Columbia, veröffentlicht wurde.

Kurz gesagt, kann dies bedeuten, dass bestimmte Probleme nur durch Brute-Force-Suche gelöst werden können, wenn Lösungen gefunden werden können alle.

"Der Beweis erforderte das Zusammensetzen von Prinzipien aus mehreren Bereichen der Mathematik. Der Hauptanstrengung bei der Konstruktion dieses Beweises war das Aufdecken einer Kette von konzeptionellen Verbindungen zwischen verschiedenen Bereichen und deren Betrachtung durch eine gemeinsame Linse", schrieb Deolalikar

Natürlich wissen diejenigen, die mit dem Problem vertraut sind, zu behaupten, dass Deolalikar das Problem gelöst hat, angesichts der Menge an Überprüfungen, die durchgeführt werden müssten. Und während sie Deolalikar für seine gründliche Herangehensweise loben, die sich von den eher zufälligen Vermutungen unterscheidet, die normalerweise präsentiert werden, hat niemand definitiv behauptet, dass er das Problem gelöst hat.

"Es scheint vor allem einige zum Nachdenken anregende neue Ideen zu geben eine Verbindung zwischen statistischer Physik und der logischen Charakterisierung erster Ordnung von NP ", schrieb Scott Aaronson, Assistant Professor für Elektrotechnik und Informatik am Massachusetts Institute of Technology, in einem unverbindlichen Blogeintrag.

" Ich weiß nicht was zu denken, aber ich bin auf jeden Fall hoffnungsvoll ", schrieb Dick Lipton, Professor für Informatik am Georgia Institute of Technology.

Joab Jackson berichtet über Unternehmenssoftware und allgemeine Technologie für The IDG News Service. Folge Joab auf Twitter unter @Joab_Jackson. Joabs E-Mail-Adresse ist [email protected]