Karp-Reduktion

Karp-Reduktion

Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann.

Polynomiell beschränkte Turingreduktionen werden auch als Cook-Reduktion bezeichnet. Meist bezieht sich der Begriff Polynomialzeitreduktion jedoch auf eine polynomiell beschränkte many-one-Reduktion (auch: Karp-Reduktion).

Polynomielle many-one-Reduktionen werden in der Komplexitätstheorie beispielsweise verwendet, um nachzuweisen, dass eine Sprache der Komplexitätsklasse NP auch NP-vollständig ist.

Schreibweisen

Es existieren unterschiedliche Schreibweisen, darunter

L \preceq_p L^\prime
L \le_{pol} L^\prime

Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

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

  • Cook-Reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Polinomielle Reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Polynomiale Reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Polynomialzeit-Reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Polynomielle Reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Polynominale reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Polynomialzeitreduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion in der theoretischen Informatik. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet… …   Deutsch Wikipedia

  • Polynomiell reduzierbar — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Satz von Cook — Der kanadische Wissenschaftler Stephen A. Cook begründete 1971 eine neue Klasse von Problemen in der Komplexitätstheorie. Er zeigte, dass eine Teilmenge der Klasse NP existiert, auf die sich alle Probleme aus NP polynomiell reduzieren lassen.… …   Deutsch Wikipedia

  • Kreiskritische Knotenmenge — Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP vollständig ist. Definition Es fragt, ob es zu einem ungerichteten Multigraphen G = (V,E) …   Deutsch Wikipedia

Share the article and excerpts

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