Complexity Classes - Models of Computation: Exploring the Power of Computing - page 352

DEFINITION 8.8.3 Problems in P that are hard for P under log-space reductions are called P-
complete .Problemsin NP that are hard for NP under polynomial-time reductions are called NP-
complete .Problemsin PSPACE that are hard for PSPACE under polynomial-time reductions are
called PSPACE-complete .

We s t a t e Theorem 8.8.2 , which follows directly from Definition 8.7.3 and transitivity of
log-space and polynomial-time reductions, because it incorporates as conditions the goals of
the study of P -complete, NP -complete, and PSPACE -complete problems, namely, to show
that all problems in P can be solved in log-space and all problems in NP and PSPACE can be
solved in polynomial time. It is unlikely that any of these goals can be reached.

THEOREM 8.8.2 If a P -complete problem can be solved in log-space, then all problems in P can
be solved in log-space. If an NP -complete problem is in P ,then P = NP .Ifa PSPACE -complete
problem is in P ,then P = PSPACE .

In Theorem 8.14.2 we show that if a P -complete problem can be solved in poly-logarithmic
time with polynomially many processors on a CREW PRAM (they are fully parallelizable),
then so can all problems in P . It is considered unlikely that all languages in P can be fully par-
allelized. Nonetheless, the question of the parallelizability of P is reduced to deciding whether
P -complete problems are parallelizable.

8.9 P -Complete Problems
To show that a problem

P is P -completewemustshowthatitisin P and that all problems

P

in P can be reduced to via a log-space reduction. (See Section 3.9.5 .) The task of showing

this is simplified by the knowledge that log-space reductions are transitive: if another problem
Q P

has already been shown to be P -complete, to show that is P -complete it suffices to show

Q P P∈

there is a log-space reduction from to and that P .

CIRCUIT VALUE
Instance: A circuit description with fixed values for its input variables and a designated
output gate.
Answer: “Yes” if the output of the circuit has value 1.

In Section 3.9.5 we show that the CIRCUIT VALUE problem described above is P -complete
by demonstrating that for every decision problem

P

in P an instance w of

P

and a DTM M

can be translated by a log-space DTM into an instance c
of CIRCUIT VALUE such that w is a “Yes” instance of

P

that recognizes “Yes” instances of

P if and only if c is a “Yes” instance of

CIRCUIT VALUE .
Since P is closed under complements (see Theorem 8.6.1 ), it follows that if the “Yes” in-
stances of a decision problem can be determined in polynomial time, so can the “No” instances.
Thus, the CIRCUIT VALUE problem is equivalent to determining the value of a circuit from its
description. Note that for CIRCUIT VALUE the values of all variables of a circuit are included
in its description.
CIRCUIT VALUE is in P because, as shown in Theorem 8.13.2 , a circuit can be evaluated
in a number of steps proportional at worst to the square of the length of its description. Thus,
an instance of CIRCUIT VALUE can be evaluated in a polynomial number of steps.