Circuit Value Problem

Das Vorlage:Lang (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 Vorlage:Lang, 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

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur