Circuit Value Problem

from Wikipedia, the free encyclopedia

The circuit value problem (CVP) is a P-complete problem.

Problem

A circuit with fixed inputs is given. In the formal language Circuit Value, an input belongs together with the circuit if the result of the circuit is 1.

Important statements and sentences

  • CVP is P-complete .
  • The CVP is also P-complete if the circuit is planar or a monotonic circuit (consists only of AND and OR gates).
  • The CVP for circuits that are monotonic and planar can be solved in LOGSPACE .

Proof idea for the sentence "CVP is P-complete"

It has to be shown that every problem of complexity class P can be reduced to CVP and that CVP lies in P.

  1. A corresponding algorithm must be specified for.
  2. The problems in P are those that can be solved by a Turing machine within polynomial time. For this reason, a function must be constructed that transfers any Turing machine with logarithmic space requirements into a circuit with fixed input, which delivers a 1 as the result exactly when the entered Turing machine stops on its input in an accepting configuration. This proof is similar to the proof of Cook's Theorem , except that part of the input of the circuit does not have to be “guessed” nondeterministically .

literature

  • K. Rüdiger Reischuk: Introduction to Complexity Theory: Volume 1: Basics of machine models , time and space complexity, nondeterminism . Teubner Verlag, 1999, ISBN 978-3-519-12275-3 , 2.2 Circuit families.
  • 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 (English).
  • Richard E. Ladner: The circuit is value problem-log space complete for P . In: ACM (Ed.): SIGACT News . tape 7 , no. 1 , 1975, p. 18-20 , doi : 10.1145 / 990518.990519 (English).

Individual evidence

  1. ↑ Leslie M. Gold hit: The monotonous and planar circuit value problems are log space complete for P . In: SIGACT News . tape 9 , no. 2 . ACM, 1977, pp. 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 . tape 80 , no. 3 . Elsevier, 1989, ISSN  0890-5401 , p. 205-226 , doi : 10.1016 / 0890-5401 (89) 90009-6 .