[schranze]

Eines der wichtigsten offenen Probleme, mit denen sich Mathematiker und theoretische Informatiker herumschlagen, scheint gelöst: die Frage, ob die beiden so genannten Komplexitätsklassen P und NP identisch sind oder nicht.

In der Komplexitätstheorie umfasst die Klasse P all die Probleme, die sich mit einer deterministischen Rechenmaschine in einer Rechenzeit t lösen lassen, die von der Größe der Eingangsdaten n höchstens polynomisch abhängt, das heißt t ≤ nk. Als Modell einer deterministischen Rechenmaschine verwenden Theoretiker üblicherweise eine Turing-Maschine, aber auch alle herkömmlichen digitalen Computer gehören dazu. Die Komplexitätsklasse P umfasst also alle Aufgabenstellungen, die sich mit vertretbarer Rechenzeit exakt berechnen lassen.

Das Dokument für die Beweisführung ist hier zu finden (hat "nur" 66 Seiten)
[ Link nur für registrierte Mitglieder sichtbar. Bitte einloggen oder neu registrieren ]