NP (Komplexitätsklasse)

NP ist eine Klasse von Problemen aus der Komplexitätstheorie, die von nichtdeterministischen Turingmaschinen in polynomieller Zeit entschieden werden kann.

Mann kann sich vorstellen, dass ein Problem in NP gelöst wird, indem ein Orakel eine Lösung für das Problem rät und eine deterministische Turingmaschine diese Lösung nur noch in Polynomialzeit verifizieren muss.

P ≠ NP !?

Ein noch offenes Problem in der Informatik ist die Frage, ob diese Klasse mit der von deterministischen Turingmaschinen in Polynomialzeit entscheidbaren Problemen (die Klasse P) übereinstimmt (das so genannte P≠NP-Dilemma).

Es ist also lediglich zu zeigen, dass das Finden einer Lösung für ein Problem wesentlich schwieriger ist, als nur zu verifizieren, ob eine gegebene Lösung korrekt ist. Dies ist allerdings bisher noch nicht gelungen. Es gibt jedoch viele Anzeichen dafür, dass tatsächlich gilt: P≠NP.