Circuit Value Problem

Circuit Value Problem (auch CVP) ist ein P-vollständiges und L-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 Eingaben und einer Ausgabe. Eine Eingabe X gehört zusammen mit dem Schaltkreis in die Sprache Circuit Value, wenn das Ergebnis des Schaltkreises 1 ist.

Siehe auch

• Komplexitätsklasse
• L (Komplexitätsklasse)
• P (Komplexitätsklasse)
• SAT

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.