Ladner-Theorem

Ladner-Theorem

Das Ladner-Theorem ist ein Satz aus der theoretischen Informatik, der sich mit der Struktur der Komplexitätsklasse NP befasst. Er wurde 1975 von Richard Ladner bewiesen.

Die Klasse NP umfasst die Komplexitätsklasse P. Die Frage, ob P eine echte Teilmenge von NP ist, ist nach wie vor offen (P-NP-Problem). Falls P≠NP, existieren sogenannte NP-vollständige Probleme. Sie bilden die Menge der schwierigsten Probleme in NP. Die Frage, ob Probleme in NP existieren, die weder NP-vollständig sind, noch in P liegen, wird vom Ladner-Theorem positiv beantwortet (falls P≠NP). Die Menge dieser Probleme wird NP-intermediate oder NPI genannt.

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 NPI liegen. Es wird jedoch vermutet, dass dies z. B. für die Primfaktorzerlegung gilt.

Literatur

  • Ladner, Richard: On the Structure of Polynomial Time Reducibility. Journal of the ACM (JACM) 22 (1): 155–171, 1975.

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Ladner — ist der Familienname folgender Personen: Gerhart B. Ladner (1905–1993), österreichisch US amerikanischer Mediävist und Kunsthistoriker Hans Ladner (1930−2001), österreichischer Bildhauer Johann Ladner (1707−1779), österreichischer Bildhauer Luca… …   Deutsch Wikipedia

  • Ladner — may refer to:People*Dr. Benjamin Ladner, an academic philosopher and theologian. *Kurt Ladner, a pen name of Nelson DeMille *Peter Ladner, Vancouver city councillor. *Richard Ladner, of Ladner s theorem in computational complexity. *Wendell… …   Wikipedia

  • Ladner's theorem — In computational complexity, Ladner s theorem asserts that, if the computational classes P and NP are not equal, the latter contains problems that are neither in P nor NP complete.Problems that are in NP but are neither in P nor NP complete are… …   Wikipedia

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

  • P versus NP problem — Unsolved problems in computer science Is P = NP ? …   Wikipedia

  • NP-intermediate — In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP complete are called NP intermediate, and the class of such problems is called NPI. Ladner s theorem, shown in 1975 by Richard… …   Wikipedia

  • Complexity of constraint satisfaction — The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction… …   Wikipedia

  • Constraint satisfaction problem — Constraint satisfaction problems (CSP)s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite… …   Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • Dynamic logic (modal logic) — For the subject in digital electronics also known as clocked logic, see dynamic logic (digital electronics). Dynamic logic is an extension of modal logic originally intended for reasoning about computer programs and later applied to more general… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”