imported>Cepheiden: Einleitung an das Lemma angepasst. Der deutschsprachige Begriff findet sich selten bis gar nicht (vor allem nicht vor des Auftretens in der Wikipedia)

2022-11-28T14:54:07Z

Einleitung an das Lemma angepasst. Der deutschsprachige Begriff findet sich selten bis gar nicht (vor allem nicht vor des Auftretens in der Wikipedia)

Neue Seite

Das {{lang|en|'''Circuit Value Problem'''}} (engl., CVP, dt. etwa: ''Schaltkreis-Auswertungsproblem'') ist in der [[Theoretische Informatik|theoretischen Informatik]] ein [[P-Vollständigkeit|P-vollständiges]] [[Problem]].

== Problemstellung ==
Gegeben ist ein [[boolescher Schaltkreis]] mit <math>n</math> festen Eingaben. Eine Eingabe <math>X</math> gehört zusammen mit dem Schaltkreis in die [[formale Sprache]] ''{{lang|en|Circuit Value}},'' wenn das Ergebnis des Schaltkreises 1 ist.

== Wichtige Aussagen und Sätze ==
* CVP ist [[P-Vollständigkeit|P-vollständig]].
* Das CVP ist auch [[P-Vollständigkeit|P-vollständig]], wenn der Schaltkreis planar ist oder ein monotoner Schaltkreis ist (nur aus AND- und OR-Gattern besteht).<ref>{{Literatur |Autor=Leslie M. Goldschlager |Titel=The monotone and planar circuit value problems are log space complete for P |Sammelwerk=SIGACT News |Band=9 |Nummer=2 |Verlag=ACM |Datum=1977 |Seiten=25–29 |DOI=10.1145/1008354.1008356}}</ref>
* Das CVP für Schaltkreise, die monoton und planar sind, kann in [[LOGSPACE]] gelöst werden.<ref>{{Literatur |Autor=Patrick W. Dymond, Stephen A. Cook |Titel=Complexity theory of parallel time and hardware |Sammelwerk=Information and Computation |Band=80 |Nummer=3 |Verlag=Elsevier |Datum=1989 |ISSN=0890-5401 |Seiten=205–226 |DOI=10.1016/0890-5401(89)90009-6}}</ref>

== Beweisidee für den Satz „CVP ist P-vollständig“ ==
Es ist zu zeigen, dass jedes Problem der [[Komplexitätsklasse]] [[P (Komplexitätsklasse)|P]] auf CVP reduziert werden kann sowie, dass CVP in P liegt.
# Für <math>\text{CVP} \in \text{P}</math> muss ein entsprechender [[Algorithmus]] angegeben 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 mit [[Logarithmisch platzbeschränkte Reduktion|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 [[Satz von Cook|Satzes von Cook]], nur dass nicht wie dort ein Teil der Eingabe des Schaltkreises [[Nichtdeterminismus|nichtdeterministisch]] „erraten“ werden muss.

== Literatur ==
* {{Literatur
|Autor=K. Rüdiger Reischuk
|Titel=Einführung in die Komplexitätstheorie: Band 1: Grundlagen Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus
|Verlag=Teubner Verlag
|Datum=1999
|ISBN=3-519-12275-8
|Kapitel=2.2 Schaltkreis-Familien}}
* {{Literatur
|Autor=[[Christos Papadimitriou|Christos H.Papadimitriou]]
|Titel=Computational Complexity
|Verlag=Addison-Wesley, Reading/Mass
|Datum=1995
|ISBN=0-201-53082-1
|Kapitel=4.3 Boolean functions and circuits & 8 Reductions and completeness
|Sprache=en}}
* {{Literatur
|Autor=Richard E. Ladner
|Hrsg=ACM
|Titel=The circuit value problem is log space complete for P
|Sammelwerk=SIGACT News
|Band=7
|Nummer=1
|Datum=1975
|Seiten=18–20
|Sprache=en
|DOI=10.1145/990518.990519}}

== Einzelnachweise ==
<references />

[[Kategorie:Komplexitätstheorie]]

Circuit Value Problem - Versionsgeschichte

imported>Cepheiden: Einleitung an das Lemma angepasst. Der deutschsprachige Begriff findet sich selten bis gar nicht (vor allem nicht vor des Auftretens in der Wikipedia)