NP-intermediate

rdf:langString Satz von Ladner

rdf:langString Der Satz von Ladner ist ein Satz aus der theoretischen Informatik, der sich mit der Struktur der Komplexitätsklasse NP in Bezug auf P befasst. Er wurde 1975 von bewiesen. Die Klasse umfasst die Komplexitätsklasse der in Polynomzeit deterministisch entscheidbaren Sprachen. Die Frage, ob eine echte Teilmenge von ist, ist nach wie vor offen (siehe P-NP-Problem). Die NP-vollständigen Probleme sind die schwierigsten Probleme in . Die Frage, ob Probleme in existieren, die weder -vollständig sind, noch in liegen, wird vom Satz von Ladner positiv beantwortet, falls gilt. Die Menge dieser Probleme wird NP-intermediate oder genannt. Der Satz lautet damit formal:. Für den Beweis des Satzes wurde von Ladner ein künstliches Problem generiert, welches keinerlei praktische Relevanz besitzt. Es ist nicht bekannt, ob auch natürliche Probleme in liegen (falls ). Es wird jedoch vermutet, dass das z. B. für die Primfaktorzerlegung gilt. Der Satz lässt sich verallgemeinern, sodass er unabhängig von der Annahme gilt: Unter Polynomialzeit-Reduktion (sowohl Turingreduktion als auch many-one-Reduktion) gibt es keine minimale Klasse über . Das heißt, wenn ein Problem echt schwerer als die Probleme in ist, dann gibt es Probleme , die ebenfalls nicht in liegen, aber echt leichter als sind.