Was ist das PCP?
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.
Wie kann man vorgehen, um zu entscheiden, ob eine konkrete Instanz des PCP lösbar ist oder nicht?
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
Charakterisieren Sie die Zeitkomplexitätsklasse NP
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
Was versteht man unter einer Polyzeit-Reduktion?
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.
Zuletzt geändertvor einem Monat