Reduktionen und Komplexität

Das Post-Korrespondenzproblem ist ein Entscheidungsproblem, bei dem man entscheiden muss, ob es möglich ist, eine bestimmte Reihenfolge von String-Paaren so zu kombinieren, dass die resultierenden Strings gleich sind.

Merkmale:

• nicht entscheidbar, da es keinen Algorithmus gibt

• PCP wird oft verwendet, um die Unentscheidbarkeit anderer Probleme zu verdeutlichen.

Es gibt keinen eindeutigen Algorithmus, der für jedes Problem des PCP lösen kann.

Es gibt dafür einige Ansätze um zu überprüfen oder zu lösen:

Brute-Force: Alle möglichen Kombinationen ausprobieren

Suchalgorithmus: Triefensuche oder Breitensuche

Reduktion auf andere Probleme

Merkmale:

• NP ist die Klasse von Entscheidungsproblemen

• Es gibt einen polynomiellen Verfikator

  Unter einem Verifikator versteht man ein Algorithmus der das Problem lösen kann und dabei in polynomieller Zeit arbeitet.

• NP kann auch als die Menge von Problemen beschrieben werden, die von einer nichtdeterminitischen Turingmaschine in polynomieller Zeit gelöst werden kann

• Polynomielle Zeitreduktion: Existenz einer polynomiellen Zeitreduktion

• Beziehung zu P: Falls P ein Problem ist gehört P auch. zu NP

• Ein Problem ist NP wenn:

  • Es in NP ist

  • Jedes Problem in NP auf dieses Problem in polynomialer Zeit reduziert werden kann

Eine Polyzeit-Reduktion ist wie eine schnelle und korrekte Umwandlung von einem Problem in ein anderes. Wenn Sie zeigen können, dass Problem A schnell in Problem B umgewandelt werden kann, und Problem B schwer zu lösen ist, dann ist auch Problem A mindestens so schwierig.