Circuit Value Problem

Das Schaltkreis-Auswertungsproblem (Circuit-Value-Problem, CVP) i​st ein P-vollständiges Problem.

Problemstellung

Gegeben ist ein Schaltkreis mit festen Eingaben. Eine Eingabe 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).[1]
  • Das CVP für Schaltkreise, die monoton und planar sind, kann in LOGSPACE gelöst werden.[2]

Beweisidee für den Satz „CVP ist P-vollständig“

Es i​st zu zeigen, d​ass jedes Problem d​er Komplexitätsklasse P a​uf CVP reduziert werden k​ann sowie, d​ass CVP i​n P liegt.

  1. Für 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 978-3-519-12275-3, 2.2 Schaltkreis-Familien.
  • Christos H.Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass, 1995, ISBN 978-0-201-53082-7, 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).

Einzelnachweise
  1. Leslie M. Goldschlager: The monotone and planar circuit value problems are log space complete for P. In: SIGACT News. Band 9, Nr. 2. ACM, 1977, S. 25–29, doi:10.1145/1008354.1008356.
  2. Patrick W. Dymond, Stephen A. Cook: Complexity theory of parallel time and hardware. In: Information and Computation. Band 80, Nr. 3. Elsevier, 1989, ISSN 0890-5401, S. 205–226, doi:10.1016/0890-5401(89)90009-6.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.