Machines with Memory - Models of Computation: Exploring the Power of Computing - page 130

The program of Fig. 3.27 provides a translation (or reduction ) from any language in NP
(or P ) to a language that we later show is a hardest language in NP (or P ).
We now us e Theorem 3.9.3 and the above facts to give a brief introduction to the P -
complete and NP -complete languages, which are discussed in more detail in Chapter 8 .

3.9.4 Definitions of P -Complete and NP -Complete Languages
In this section we identify languages that are hardest in the classes P and NP . A language L 0 is
hardest in one of these classes if a) L 0 is itself in the class and b) for every language L in the
class, a test for the membership of a string w in L can be constructed by translating w with an
algorithm to a string v and testing for membership of v in L 0 .Iftheclassis P ,thealgorithm
must use at most space logarithmic in the length of w , whereas in the case of NP ,thealgorithm
must use time at most a polynomial in the length of w . Such a language L 0 is said to be a
complete language for this complexity class. We begin by defining the P -complete languages.

DEFINITION 3.9.1 A language L ⊆B ∗ is P-complete if it is in P and if for every language
L 0 ⊆B ∗ in P , there is a log-space deterministic program that translates each w

∈B ∗ into a string

w ∈B ∗ such that w L 0 if and only if w ∈ ∈ L .

The NP -complete languages have a similar definition. However, instead of requiring that
the translation be log-space, we ask only that it be polynomial-time. It is not known whether
all polynomial-time computations can be done in logarithmic space.

DEFINITION 3.9.2 A language L ⊆B ∗ is NP-complete if it is in NP and if for every language
L 0 ⊆B ∗ in NP , there is a polynomial-time deterministic program that translates each w ∈B ∗

into a string w ∈B ∗ such that w L 0 if and only if w ∈ ∈ L .

Space precludes our explaining the important role of the P -complete languages. We simply
report that these languages are the hardest languages to parallelize and refer the reader to Sec-
tions 8.9 and 8.14.2 . However, we do explain the importance of the NP -complete languages.
As the following theorem states, if an NP -complete language is in P ; that is, if membership
of a string in an NP -complete language can be determined in polynomial time, then the same
canbedoneforeverylanguagein NP ;thatis, P and NP are the same class of languages.
Since decades of research have failed to show that P = NP , a determination that a problem is
NP -complete is a testimonial to but not a proof of its difficulty.

THEOREM 3.9.4 If an NP -complete language is in P ,then P = NP .
Proof Let L be NP -complete and let L 0 be an arbitrary language in NP .Because L is NP -
complete, there is a polynomial-time program that translates an arbitrary string w into a
string w

such that w ∈

L if and only if w ∈ L 0 .If L ∈

P , then testing of membership
of strings in L 0 can be done in polynomial time in the length of the string. It follows that
there exists a polynomial-time program to determine membership of a string in L 0 .Thus,
every language in NP is also in P .

3.9.5 Reductions to P -Complete Languages
We now formally define CIRCUIT VALUE ,ourfirst P -complete language.