Schaltkreis-Auswertungsproblem

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.

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.

1. Für CVP ∈ P muss ein entsprechender Algorithmus angeben werden.
2. 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 ä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