Circuit Value Problem

Das Circuit Value Problem (engl., CVP, dt. etwa: Schaltkreis-Auswertungsproblem) ist in der theoretischen Informatik ein P-vollständiges Problem.

Problemstellung

Gegeben ist ein boolescher 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.
• Das CVP ist auch P-vollständig, wenn der Schaltkreis planar ist oder ein monotoner Schaltkreis ist (nur aus AND- und OR-Gattern besteht).
• Das CVP für Schaltkreise, die monoton und planar sind, kann in LOGSPACE gelöst werden.

Beweisidee für den Satz „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 ${\text{CVP}}\in {\text{P}}$ muss ein entsprechender Algorithmus angegeben 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 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 Satzes von Cook, nur dass nicht wie dort ein Teil der Eingabe des Schaltkreises nichtdeterministisch „erraten“ werden muss.

Literatur

• K. Rüdiger Reischuk: Einführung in die Komplexitätstheorie: Band 1: Grundlagen Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus. Teubner Verlag, 1999, ISBN 3-519-12275-8, 2.2 Schaltkreis-Familien. 
• Christos H.Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass, 1995, ISBN 0-201-53082-1, 4.3 Boolean functions and circuits & 8 Reductions and completeness (englisch). 
• Richard E. Ladner: The circuit value problem is log space complete for P. In: ACM (Hrsg.): SIGACT News. Band 7, Nr. 1, 1975, S. 18–20, doi:10.1145/990518.990519 (englisch).