"§"
P ungleich NP (W3)
"P ungleich NP" steht für die Aussage:
Die Komplexitätsklasse P umfasst alle Aufgabenstellungen, die sich mit vertretbarer Rechenzeit exakt berechnen lassen.
Die Komplexitätsklasse NP umfasst alle Aufgabenstellungen, die sich mit vertretbarer Rechenzeit mit einer nichtdeterministischen Turing-Maschine berechnen lassen.
(E?)(L?) http://www.heise.de/newsticker/meldung/P-NP-moeglicherweise-bewiesen-1052857.html
(E?)(L?) http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf
...
P ist eine Teilmenge von NP, denn Probleme, die sich deterministisch in Polynomialzeit lösen lassen, können auch nichtdeterministisch mit polynomischem Aufwand berechnet werden. Die bislang unbeantwortete Frage lautet, ob das auch umgekehrt gilt oder nicht.
Etwas salopp formuliert: Könnten nichtdeterministische Maschinen bestimmte Rechenprobleme schneller lösen als bisherige Computer? Genau diese Frage bejaht Deolalikar nun in seinem Papier.
Die Arbeit ist ganz frisch und noch nicht ausführlich von Kollegen geprüft. Der HP-Forscher gilt aber als Experte auf diesem Forschungsgebiet und erste Einschätzungen halten die Arbeit für stichhaltig. Ob sie genaueren Prüfungen standhält, wird sich noch zeigen müssen, aber dass es diese Prüfungen geben wird, kann als sicher gelten: Immerhin ist das P-NP-Problem eines von sieben Fragestellungen, die das Clay Mathematics Institute (CMI) in Cambridge in die Liste der so genannten Millennium-Probleme aufgenommen und für deren Lösung es jeweils ein Preisgeld von einer Million US-Dollar ausgelobt hat. (hos)
...
P <> NP
Vinay Deolalikar
HP Research Labs, Palo Alto
August 6, 2010
Abstract
We demonstrate the separation of the complexity class NP from its subclass P. Throughout our proof, we observe that the ability to compute a property on structures in polynomial time is intimately related to the statistical notions of conditional independence and sufficient statistics. The presence of conditional independencies manifests in the form of economical parametrizations of the joint distribution of covariates. In order to apply this analysis to the space of solutions of random constraint satisfaction problems, we utilize and expand upon ideas from several fields spanning logic, statistics, graphical models, random ensembles, and statistical physics.
...
Erstellt: 2010-08