Polynomialzeitreduktion

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 werden kann.

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

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:

  • NP-Vollständig — Der Begriff NP Vollständigkeit ist ein Begriff aus der Komplexitätstheorie der Theoretischen Informatik, der im Jahre 1971 von Stephen A. Cook durch den Satz von Cook eingeführt wurde. Er zeichnet spezielle formale Sprachen der Komplexitätsklasse …   Deutsch Wikipedia

  • NP-vollständig — Der Begriff NP Vollständigkeit ist ein Begriff aus der Komplexitätstheorie der Theoretischen Informatik, der im Jahre 1971 von Stephen A. Cook durch den Satz von Cook eingeführt wurde. Er zeichnet spezielle formale Sprachen der Komplexitätsklasse …   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

  • Erfüllbarkeitsproblem — Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von engl. satisfiability) ist ein Entscheidungsproblem. Es fragt, ob eine aussagenlogische Formel erfüllbar ist. Anwendungen finden sich unter anderem in der Komplexitätstheorie, Verifikation und… …   Deutsch Wikipedia

  • HORNSAT — Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von engl. satisfiability) ist ein Entscheidungsproblem. Es fragt, ob eine aussagenlogische Formel erfüllbar ist. Anwendungen finden sich unter anderem in der Komplexitätstheorie, Verifikation und… …   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

  • NP-Vollständigkeit — Die Bezeichnung NP Vollständigkeit (nichtdeterministisch polynomielle Vollständigkeit) ist ein Fachausdruck aus der Komplexitätstheorie der Theoretischen Informatik. NP vollständige Probleme lassen sich vermutlich nicht effizient lösen. Der… …   Deutsch Wikipedia

  • P!=NP — Das P NP Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie. Es stellt die Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden… …   Deutsch Wikipedia

  • P/NP-Problem — Das P NP Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie. Es stellt die Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden… …   Deutsch Wikipedia

  • P=NP — Das P NP Problem (auch P≟NP, P versus NP) ist ein ungelöstes Problem der Mathematik und theoretischen Informatik, speziell der Komplexitätstheorie. Es stellt die Frage, ob Probleme existieren, für die eine gegebene Lösung leicht überprüft werden… …   Deutsch Wikipedia

Share the article and excerpts

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