Polynomialzeit-Reduktion

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 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:

  • Reduktion (Theoretische Informatik) — Die Reduktion ist eine Methode der Theoretischen Informatik. Eine Reduktion ist die Lösung eines Problems mit Hilfe eines hypothetischen Algorithmus für ein anderes Problem. Die Reduzierbarkeit ist somit eine Relation zwischen zwei Problemen.… …   Deutsch Wikipedia

  • 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

  • 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… …   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

  • 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

  • Parametrisierter Algorithmus — Die parametrisierte Algorithmik ist ein relativ junges Teilgebiet der theoretischen Informatik, in dem genauer untersucht wird, welche Instanzen von NP vollständigen Problemen effizient zu lösen sind. Dabei wird untersucht, von welchen Faktoren… …   Deutsch Wikipedia

  • Turingreduktion — Die Reduktion ist eine Methode der Theoretischen Informatik. Eine Reduktion ist die Lösung eines Problems mit Hilfe eines hypothetischen Algorithmus für ein anderes Problem. Die Reduzierbarkeit ist somit eine Relation zwischen zwei Problemen.… …   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

Share the article and excerpts

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