heise online – P != NP möglicherweise bewiesen

Ich finde, das Problem fängt jetzt erst an. 😉 „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.“

heise online – P != NP möglicherweise bewiesen

Dieser Beitrag wurde unter Wissenschaft abgelegt und mit verschlagwortet. Setze ein Lesezeichen auf den Permalink.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.