Was ist das P-NP-Problem? Das ungelöste Problem der Komplexitätstheorie und der Unterschied zwischen Klasse P und NP leicht verständlich erklärt

Bietet einen leicht verständlichen Überblick über das größte ungelöste Problem der Informatik, das „P-NP-Problem“, aus der Perspektive deterministischer Turingmaschinen, und erklärt dabei den Unterschied zwischen „Klasse P“, die in Polynomzeit gelöst werden kann, und „Klasse NP“, deren Lösungsgültigkeit in Polynomzeit verifiziert werden kann.

Ü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.

Referenzseite : https://daigakudenki.com/np-hard/