ил. COMPLEMENTS OF LANGUAGES IN иг

However, we should bear in mind that, should P turn out to equal AfV, then all three classes are actually the same.

NP-complete problems

Complements of NP-complete problems

Figure 11.1: Suspected relationship between co-AfV and other classes of languages

Example 11.1: Consider the complement of the language SAT, which is surely a member of co-AfP. We shall refer to this complement as i75AT (unsatisfiable). The strings in USAT include all those that code boolean expressions that are not satisfiable. However, also in USAT are those strings that do not code valid boolean expressions, because surely none of those strmgs are in SAT. We believe that USAT is not ui AfV, but there is no proof

Another example of a problem we suspect is in co-AfV but not in AfV is TAUT, the set of all (coded) boolean expressions that are tautoiogies; i.e., they are true for every truth assigrunent. Note that an expression E is a tautology if and only if ~-E is unsatisfiable. Thus, TAUT and USAT are related in that whenever boolean expression E is in TAUT, ->E is in USAT, and vice-versa. However, USAT also contains strings that do not represent valid expressions, while all strings in TAUT are valid expressions. □

11.1.2 NP-Complete Problems and Co-AfT

Let us assume that V ф NV. It is still possible that the situation regarding СО-ЯР is not exactly as suggested by Fig. 11.1, because we could have ЯР and co-MV equal, but larger than V. That is, we might discover that problems Uke USAT and TAUT can be solved in nondeterministic polynomial time (i.e., they

are in AfP), and yet not be able to solve them in deterministic polynomial time. However, the fact that we have not been able to find even one NP-complete problem whose complement is in MP is strong evidence that MP Ф co-MP, as we prove in the next theorem.

Theorem 11.2 : MP - co-MP if and only if there is .some NP-complete problem whose complement is in MP.

PROOF: (OnJy-if) Should MP and co-MP be the same, then surely every NP-complete problem L, being in MP, is also in co-MP. But the complement of a problem in co-MP is in MP, so the complement of L is in MP.

(If) Suppose P is an NP-complete problem whose complement P is in MP. Then for every language L in MP, there is a polynomial-time reduction of L to P. The same reduction also is a polynomial-time reduction of L to P. We prove that MP = co-MP by proving containment in both directions.

MP С co-MP: Suppose L is in MP. Then I is in co-MP. Combine the polynomial-time reduction of L to F with the assumed nondeterministic, polynomial-time algorithm for P to yield a nondeterministic, polynomial-time algorithm for L. Hence, for any L in MP, L is also in MP. Therefore L, being the complement of a language in MP, is in co-MP- This observation tells us that MP С co-MP.

co-MP с MP: Suppose L is in co-MP. Then there is a polynomial-time reduction of L to P, since P is NP-complete, and L is in MP. This reduction is also a reduction of L to P. Since P is in MP, we combine the reduction with the nondeterministic, polynomial-time algorithm for P to show that L is in MP. □

11.1.3 Exercises for Section 11.1

! Exercise 11.1.1: Below are some problems. For each, tell whether it is in MP and whether it is in co-MP. Describe the complement of each problem. If either the problem or its complement is NP-complete, prove that as well.

* a) The problem TRUE-SAT: given a boolean expression E that is true when all the variables are made true, is there some other truth assignment besides all-true that makes E true?

b) The problem FALSE-SAT: given a boolean expression E that is false when all its variables are made false, is there some other truth assignment besides all-false that makes E false?

c) The problem DOUBLE-SAT: given a boolean expression E, are there at least two truth assignments that make E true?

d) The problem NEAR-TAUT: given a boolean expression E, is there at most one truth assignment that makes E false?

Yoq may see this class written as FSPACE in other works On the subject. However, we prefer to use the script VS to denote tiie clas.s of problems solved in deterministic (or nondeterministic) polynomial time, as we shall drop the use of AfVS once tho equivalence VS = Mrs has been proved.

*! Exercise 11.1.2: Suppose there were a function / that is a one-one function from Ti-bit integers to n-bit integers, such that:

1. f{x) can be computed in polynomial time,

2. cannot be computed in polynomial time.

Show that the language consisting of pairs of integers (x, y) such that

ГЧх)<у would then be in {AfP П co-AfV) - P.

11.2 Problems Solvable in Polynomial Space

Now, let us look at a class of problems that includes all of AfV, and appears to include more, although we cannot be certain it does. This class is defined by allowing a Turing machine to use an amount of space that is polynomial in the size of its input, no matter how much time it uses. Initially, we shall distinguish between the languages accepted by deterministic and nondeterministic TMs with a polynomial space bound, but we shall soon see that these two classes of languages are the same.

There are complete problems P for polynomial space, in tho sense that all problems m this class are reducible in polynomial time to P. Thus, if P is in V or in MV, then all languages with polynomial-space-boundcd TMs are in V or respectively. We shall offer one example of sucli a problem: quantified boolean formulas.

11.2.1 Polynomial-Space Turing Machines

A polynomial-space-bounded Turing machine is suggested by Fig. 11.2. There is some polynomial p(n) such that when given input w of length n, the TM never visits more than p(n) cells of its tape. By Theorem 8.12, we may assume that the tape is semi-infinite, and the TM never moves left from the beginning of its input.

Define the class of languages PS (polynomial space) to include all and only the languages that are L(M) for some polynomial-space-bounded, deterministic Turing machine M. .Also, define the class AfVS (nondeterministic polynomial space) to consist of those languages that are L(M) for some nondeterministic, polynomial-space-bounded TM M. Evidently VS С AfVS, since every deterministic TM is technically nondeterministic also. However, we shall prove the surprising result that VS = AlPS.