- Circuit Value Problem
-
Das Schaltkreis-Auswertungsproblem (Circuit-Value-Problem, CVP) ist ein P-vollständiges Problem. Es ähnelt stark dem Erfüllbarkeitsproblem der Aussagenlogik (SAT) mit dem Unterschied, dass bei diesem Problem keine geeignete Belegung "erraten" werden muss.
Inhaltsverzeichnis
Problemstellung
Gegeben ist ein Schaltkreis mit n festen Eingaben. Eine Eingabe X gehört zusammen mit dem Schaltkreis in die formale Sprache Circuit Value, wenn das Ergebnis des Schaltkreises 1 ist.
Wichtige Aussagen und Sätze
- CVP ist P-vollständig.
Beweisidee für CVP ist P-vollständig
Es ist zu zeigen, dass jedes Problem der Komplexitätsklasse P auf CVP reduziert werden kann, sowie dass CVP in P liegt.
- Für CVP ∈ P muss ein entsprechender Algorithmus angeben werden.
- Die Probleme in P sind diejenigen, die sich innerhalb Polynomialzeit durch eine Turingmaschine lösen lassen. Aus diesem Grund muss eine Funktion konstruiert werden, die mit logarithmischem Platzbedarf eine beliebige Turingmaschine in einen Schaltkreis mit fester Eingabe überführt, der genau dann als Ergebnis eine 1 liefert, wenn die eingegebene Turingmaschine auf ihrer Eingabe in einer akzeptierenden Konfiguration hält. Dieser Beweis ist ähnlich zum Beweis des Satz von Cook, nur dass nicht wie dort ein Teil der Eingabe des Schaltkreises nichtdeterministisch "erraten" zu werden braucht.
Literatur
- K. Rüdiger Reischuk: Komplexitätstheorie - Band I: Grundlagen : Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus. 2. Auflage. Teubner, Stuttgart/Leipzig 1999, ISBN 3-519-12275-8.
- Christos H. Papadimitriou: Computational Complexity. Addison Wesley, Reading, Massachusetts 1994, ISBN 978-0201530827
Wikimedia Foundation.
