Theorem 7.39

Theorem 7.40

Recall that the following problem is complete for P under the -reduction:

CIRCUIT VALUE PROBLEM (CVP): Given a circuit C and an input x to the circuit, determine whether the output of C is 1 or 0.

Suppose, by way of contradiction, that a sparse set S is -hard for P. We will show that CVP . To do so, we need to introduce a variation of the problem CVP.

PARITY-CVP: Given a circuit C of n gates , an input x to the circuit, a subset , and , determine whether , where denotes the exclusive-or operation and is the value of gate g_i when C receives the input x.

It is clear that and so via a log-space computable function f. For any fixed C and x, let

As S is sparse, there exists a polynomial p such that

Note that and so many elements in A_C,x are mapped by f to the same string in S. For each pair of and with , we obtain an equation

7.1

where . (Note that this is true whether or not .)

The idea of the proof is to use the above property to find many equations of the form (7.1) and then explore the local relations between the gates and these equations to determine the value of the output gate. More precisely, let us assume that we can find enough equations to form a system of linear equations of rank , with . Then, we can find the values of the gates of C on input x as follows:

1. Find many gates such that their coefficients in the system of equations form a submatrix of rank .
2. Solve the system of equations to find the values of the gates .
3. For each of the 2^t many possible Boolean assignments of the remaining gates, check whether the values of gates are consistent with the local relations defined by C (such as ).

We remark that the problems of finding the rank of a given Boolean matrix and of solving a full-rank system of equations over are both known to be in NC² (see Mulmuley (1987) and Borodin et al. (1982)). In addition, checking the local relations of gate values can be done in NC¹, and the loop (3) of cycling through 2^t Boolean assignments can be made parallel. Therefore, the whole procedure above can be implemented in NC².

From the above analysis, all we need to do is to find polynomially many subsets I of gates that are guaranteed to generate a system of equations of rank at least . For people who are familiar with the idea of randomization, it is not hard to see that a randomly selected collection of subsets I is sufficient. In the following, we use the theory of linear algebra to derandomize this selection process to get a deterministic selection of subsets I that will generate the desired system of equations.

First, we note that each subset I of gates can be represented by an n-dimensional vector over the Galois field such that each component corresponds to a gate and a component has value 1 if and only if the corresponding gate is in the subset. Let denote the n-dimensional vector space over . Denote and . Consider the Galois field as an m-dimensional vector space over . Choose any basis . Then every vector u in can be represented as , with . We can also define an inner product

for and , where all arithmetics are done in .

Now, for any , define a vector

in , and let . Clearly, . An important property of D is as follows.

Theorem 7.42

The main idea of the proof of Theorem 7.42 remains the same. It, however, involves much more work on computational linear algebra and we omit it here.

Exercises

7.1 Prove that if and , then .

7.2 A set A is called a cylinder if for some set B. Show that the following four conditions are equivalent:

1. A is a cylinder.
2. For any B, .
3. .
4. A is paddable.

7.3 Show that A is a cylinder if and only if both and are cylinders.

7.4 Show that for every subset B of a paddable -complete set A in NP, if B is in class P, then there exists a subset C of A such that , , and is infinite.

7.5 Show that every paddable -complete set A in NP has an infinite p-immune subset B in EXP.

7.6 Show that if A is c-, d-, or tt-self-reducible and , then B is also c-, d-, or tt-self-reducible, respectively.

7.7 A set L is T-self-reducible if there is a polynomially related ordering on and a polynomial-time oracle TM M such that , where . Show that a T-self-reducible set must be in PSPACE.

7.8 Complete the proof of Theorem 7.22(b).

7.9 Show that if B has subexponential density and via an almost one-to-one function f, then A also has subexponential density. In the following four exercises, we study the notion of creative sets. In these four exercises, we let p_k,i denote the polynomial , where .

7.10 Let be a recursive enumeration of polynomial-time DTMs with the runtime of M_i bounded by . A set A is called p-creative for P if there exists a polynomial-time computable function f such that

1. Show that a set is p-creative for P if and only if A is -complete for EXP.
2. Show that A is p-creative for P if and only if there exists a polynomial-time computable function f such that
   

7.11 Let be a recursive enumeration of polynomial-time NTMs with the runtime of N_i bounded by . A set A is called p-creative for NP if there exists a polynomial-time computable function f such that

1. Show that a set is p-creative for NP if and only if A is -complete for NEXP.
2. Show that a set A is p-creative for NP if and only if there exists a polynomial-time computable function f such that
   

7.12 Let be a recursive enumeration of polynomial-time NTMs and k a positive integer. A set A is called a k-creative set if there exists a polynomial-time computable function f such that for all i, if N_i has a time bound , then

1. Let f be a polynomially honest polynomial-time computable function. Define accepts f(i) in time . Show that is a k-creative set for each k ≥ 1.
2. Show that for every k ≥ 1, a k-creative set is -hard for NP.
3. Define accepts (i,x) within time . Show that A^k is a -creative set in NP.

7.13 Let . Prove that if A is k-creative and via f, which is computable in time (), then B is -creative.

7.14 Prove that an NP-complete set A is weakly paddable if and only if .

7.15 Prove that, for any k ≥ 1, a sparse set cannot be -complete for NP unless .

7.16 A set is p-selective if there is a polynomial-time computable function such that (i) for any , , and (ii) or implies .

1. Prove that if A is p-selective, then .
2. Prove that a p-selective set cannot be -hard for NP if , and it cannot be -hard for PSPACE if .

7.17 We extend the notions of immunity and bi-immunity to general complexity classes. That is, a set A is immune relative to the complexity class if any subset which is in class must be a finite set. A set S is bi-immune relative to if both A and are immune relative to .

1. Show that if is fully time constructible and , then there exists a set that is bi-immune relative to .
2. Show that there exists a set that is immune relative to NP.

7.18 We say a set X is a (polynomial-time) complexity core of set A if, for any DTM M that accepts A and any polynomial p, M(x) does not halt in time for all but a finite number of . For instance, if is bi-immune, then is a complexity core of A.

1. Show that for any , A has an infinite complexity core.
2. We say is a maximal subset of property if B has property and, for all that have property , is finite. Let A be an infinite recursive set. Prove that A has a maximal subset B in P if and only if A has a maximal complexity core .
3. Show that if is length-increasingly paddable, then A does not have a maximal subset in P. (Such a set is called P-levelable.)

7.19 Prove that if EXP contains two non-p-isomorphic -complete sets A and B, then there exist an infinite number of sets , all -complete for EXP but pairwisely non-p-isomorphic.

1. a. Show that if a set A is -complete for r.e. sets, then it is -complete for r.e. sets.
2. Show that if a set A is -complete for EXP, then it is -complete for EXP.

7.21 Prove Theorem 7.39.

7.22 Show that there exists an infinite number of sets such that all of them are -complete for EXP but are pairwisely nonequivalent under the -reducibility.

7.23 Discuss the polynomial-time isomorphism of PSPACE-complete sets. Check whether the results on collapsing degrees hold for the class PSPACE.

7.24 Prove that there exists a bi-immune set A in EXP that is not strongly bi-immune.

1. a. Prove that there exists a P-immune set A that is -complete for EXP. Therefore, there exists a set B that is -complete for EXP but not -complete for EXP.
2. Compare complete sets in EXP under the following reducibility: , , , and . More precisely, show that the classes of complete sets for EXP under these different notions of reducibility are all distinct.

1. a. Prove Theorem 7.42.
2. Prove that if , then a sparse set cannot be -hard for P for any k ≥ 1.

Historical Notes

It has been noticed by many people, including Simon (1975) and Berman (1977), that many reductions among natural NP-complete problems are actually much stronger than the requirement of a -reduction. Berman and Hartmanis (1977) proved the polynomial-time version of the Bernstein–Schröder–Cantor theorem, established the technique of paddability, and proposed the Berman–Hartmanis conjecture. The recursive version of this conjecture, that all -complete r.e. sets are recursively isomorphic, is known to be true (Myhill, 1955). Berman and Hartmanis (1977) also proposed the weaker density conjecture, that sparse sets cannot be -complete for NP. Berman (1978) was the first to use the self-reducibility property to attack the density conjecture. He showed that if , then tally sets cannot be -complete for NP. Meyer and Paterson (1979) and Ko (1983) further studied the general notion of self-reducibility. Meyer and Paterson (1979) and Fortune (1979) used the generalized self-reducibility to improve Berman's (1978) result. The density conjecture was proved to be equivalent to by Mahaney (1982). Our proof of Theorem 7.24 is based on the new technique of Ogiwara and Watanabe (1991). The related result, that sparse sets cannot be -complete for NP if , was proved in Chapter 6. Selman (1979) introduced p-selective sets. Exercise 7.16 is from Selman (1979) and Ko (1983).

Berman and Hartmanis (1977) proved that the weaker density conjecture holds true for the class EXP. The notions of P-immune sets, bi-immune sets, and strongly bi-immune sets have been studied in Berman (1976), Ko and Moore (1981), and Balcázar and Schöning (1985). Theorem 7.28 was first proved in Berman (1976) and strengthened by Balcázar and Schöning (1985). Exercise 7.25 is from Ko and Moore (1981) and Watanabe (1987). The notion of complexity cores was first defined in Lynch (1975). It has been further studied in Du et al. (1984), Ko (1985b), Orponen and Schöning (1986), Orponen, Russo, and Schöning (1986) and Du and Book (1989). Exercise 7.18 is from Du et al. (1984) and Orponen, Russo, and Schöning (1986).

Berman and Hartmanis (1977) also pointed out that all -complete sets for EXP are -equivalent. Our proof of Theorem 7.35 is based on a simplified proof given by Watanabe (1985). The relationship between one-way functions and the Berman–Hartmanis conjecture was first suggested by Joseph and Young (1985). They constructed a special type of NP-complete sets, called k-creative sets, and conjectured that if one-way functions exist, then k-creative sets are not polynomial-time isomorphic to SAT and, hence, the Berman–Hartmanis conjecture fails. Wang (1991, 1992, 1993) further studied the notion of creative sets and polynomial-time isomorphism. Selman (1992) surveyed the role of one-way functions in complexity theory. Theorem 7.38 was proved by Ko et al. (1986), and Theorem 7.39 was proved by Kurtz et al. (1988). Kurtz et al. (1990) included a survey of results in this direction. Exercise 7.20 is from Homer et al. (1993).

Hartmanis (1978) conjectured that there is no sparse P-complete set under log-space many-one reduction. Ogihara (1995) showed that the Hartmanis conjecture is true if . Cai and Sivakumar (1995) improved this result by showing that the Hartmanis conjecture is true if . Cai and Ogihara (1997) and van Melkebeek and Ogihara (1997) provide surveys in this direction.

The Berman–Hartmanis conjecture has also been studied in the relativized form. It has been shown to hold relative to some oracles (see Kurtz (1983), Kurtz et al. (1989), and Hartmanis and Hemachandra (1991)) and also to fail relative to some other oracles (see Goldsmith and Joseph (1986) and Fenner et al. (1992)). Rogers (1995) found an oracle relative to which the Berman–Hartmanis conjecture fails but one-way functions exist. Wang and Belanger (1995) studied the isomorphism problem with respect to random instances.