Überblick

1

Die Klasse P ist die Klasse von Problemen, die in polynomieller Zeit von einer deterministischen Turingmaschine entschieden werden können, und die Klasse NP ist die Klasse von Problemen, bei denen bei Vorliegen eines Beweises (genannt Witness oder Zeuge) für die Antwort "Ja" die Gültigkeit des Witness in polynomieller Zeit beurteilt (das nennt man Verifikation) werden kann. Da in polynomieller Zeit entscheidbare Probleme in polynomieller Zeit verifiziert werden können, ist offensichtlich P⊆NP, aber es ist nicht klar, ob P eine echte Teilmenge von NP ist. Es gibt noch keinen Beweis, aber viele Forscher glauben, dass P≠NP ist. Die Vermutung, dass diese Klasse P und Klasse NP nicht gleich sind, wird als "P≠NP-Vermutung" bezeichnet.