Circuit Value Problem
aus Wikipedia, der freien Enzyklopädie
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 |
[Bearbeiten] 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.
[Bearbeiten] Wichtige Aussagen und Sätze
- CVP ist P-vollständig.
[Bearbeiten] 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 in Polynomialzeit eine beliebige Turingmaschine in einen Schaltkreis mit fester Eingabe überführt. Dieser Beweis ist äquivalent zum Satz von Cook, nur das die Eingabe des Schaltkreises nicht nichtdeterminitisch "erraten" wird.
[Bearbeiten] 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, ISBN 978-0201530827
