In this section, we need some of the grouptheoretic and graphtheoretic foundations presented in Section 7.1.3 In particular, recall the notion of permutation group from Definition 7.6 and the graph isomorphism problem (, for short) and the graph automorphism problem (, for short) from Definition 7.8; see also Example 7.4 in Chapter 7. We start by providing some more background from complexity theory.
In Section 8.2, we have seen that the problems and are NPcomplete. Clearly, if and only if every NP problem (including the NPcomplete problems) is in P, which in turn is true if and only if some NPcomplete problem is in P. So, no NPcomplete problem can be in P if . An interesting question is whether, under the plausible assumption that , every NP problem is either in P or NPcomplete. Or, assuming , can there exist NP problems that are neither in P nor NPcomplete? A result by Ladner [ 157 ] answers this question.
Theorem 8.7 (Ladner) If then there exist sets in NP that are neither in P nor NPcomplete.
The problems constructed in the proof of Theorem 8.7 are not overly natural problems. However, there are also good candidates of “natural” problems that are neither in P nor NPcomplete. One such candidate is the graph isomorphism problem. To provide some evidence for this claim, we now define two hierarchies of complexity classes, the low hierarchy and the high hierarchy, both introduced by Schöning [ 226 ]. First, we need to define the polynomial hierarchy, which builds upon NP. And to this end, we need a more flexible reducibility than the (polynomialtime) manyone reducibility from Definition 8.4, namely the Turing reducibility . We will also define the (polynomialtime) nondeterministic Turing reducibility, , and the (polynomialtime) strong nondeterministic Turing reducibility, . These two reducibilities are important for the polynomial hierarchy and for the high hierarchy, respectively. Turing reducibilities are based on the notion of oracle Turing machines, which we now define.
Definition 8.8 (Oracle Turing machine) An oracle set is a set of strings. An oracle Turing machine , with oracle , is a Turing machine that has a special worktape, which is called the oracle tape or query tape. In addition to other states, contains a special query state, , and the two answer states and . During a computation on some input, if is not in the query state , it works just like a regular Turing machine. However, when enters the query state , it interrupts its computation and queries its oracle about the string currently written on the oracle tape. Imagine the oracle as some kind of “black box”: answers the query of whether or not it contains within one step of 's computation, regardless of how difficult it is to decide the set . If , then changes its current state into the new state and continues its computation. Otherwise, if , continues its computation in the new state . We say that the computation of on input is performed relative to the oracle , and we write .
The language accepted by is denoted . We say a language is represented by an oracle Turing machine if and only if . We say a class of languages is relativizable if and only if it can be represented by oracle Turing machines relative to the empty oracle. For any relativizable class and for any oracle , define the class relative to by
For any class of oracle sets, define .
Let NPOTM (respectively, DPOTM) be a shorthand for nondeterministic (respectively, deterministic) polynomialtime oracle Turing machine. For example, the following classes can be defined:
For the empty oracle set , we obtain the unrelativized classes and , and we then write NPTM instead of NPOTM and DPTM instead of DPOTM.
In particular, oracle Turing machines can be used for prefix search. Let us consider an example.
Example 8.3 (Prefix search by an oracle Turing machine)
Suppose we wish to find the smallest solution of the graph isomorphism problem, which is in NP; see Definition 7.8 in Subsection 7.1.3. Let and be two given graphs with vertices each. An isomorphism between and is called a solution of “ ”. The set of isomorphisms between and , , contains all solutions of “ ”.
Our goal is to find the lexicographically smallest solution if ; otherwise, we output the empty string to indicate that . That is, we wish to compute the function defined by if , and if , where the minimum is to be taken according to the lexicographic order on . More precisely, we view a permutation as the string of length over the alphabet , and we write for if and only if there is a such that for all and .
From a permutation , one obtains a partial permutation by cancelling some pairs . A partial permutation can be represented by a string over the alphabet , where indicates an undefined position. Let . A prefix of length of is a partial permutation of containing each pair with , but none of the pairs with . In particular, for , the empty string is the (unique) length prefix of . For , the total permutation is the (unique) length prefix of itself. Suppose that is a prefix of length of and that is a string over of length with none of the occurring in . Then, denotes the partial permutation that extends by the pairs . If in addition for , then is also a prefix of . For our prefix search, given two graphs and , we define the set of prefixes of the isomorphisms in by
Note that, for , the empty string does not encode a permutation in . Furthermore, if and only if , which in turn is true if and only if .
Starting from the empty string, we will construct, bit by bit, the smallest isomorphism between the two given graphs (if there exists any). We below present an DPOTM that, using the NP set as its oracle, computes the function by prefix search; see also Exercise 8.42. Denoting the class of functions computable in polynomial time by , we thus have shown that is in . Since is in NP (see Exercise 8.42), it follows that is in .
NPreIso(
)
1IF
2THEN
RETURN
3ELSE
4 5WHILE
and have vertices each. 6DO
7WHILE
8DO
9 10 11RETURN
Example 8.3 shows that also Turing machines computing functions can be equipped with an oracle, and that also function classes such as can be relativizable. We now return to oracle machines accepting languages and use them to define several reducibilities. All reducibilities considered here are polynomialtime computable.
Definition 8.9 (Turing reducibilities) Let be a binary alphabet, let and be sets of strings over , and let be any complexity class. The set of complements of sets in is defined by .
Define the following reducibilities:
Turing reducibility: for some DPOTM .
Nondeterministic Turing reducibility: for some NPOTM .
Strong nondeterministic Turing reducibility: .
Let be one of the reducibilities defined above. We call a set hard for if and only if for each set . A set is said to be complete in if and only if is hard for and .
is the closure of under the reducibility.
is the closure of under the reducibility.
Using the reducibility and the reducibility introduced in Definition 8.9, we now define the polynomial hierarchy, and the low and the high hierarchy within NP.
Definition 8.10 (Polynomial hierarchy) Define the polynomial hierarchy PH inductively as follows: , , and for , and .
In particular, and and . The following theorem, which is stated without proof, provides some properties of the polynomial hierarchy, see Problem 82.
Theorem 8.11 (Meyer and Stockmeyer) For all holds:
1. .
2. , , , and are closed under reductions. is even closed under reductions.
3. contains exactly those sets for which there exist a set in P and a polynomial such that for each :
where the quantifiers and are polynomially lengthbounded, and if is odd, and if is even.
4. If for some , then collapses to .
5. If for some , then collapses to .
6. There are complete problems for each of the classes , , and . In contrast, if has a complete problem, then collapses to a finite level, i.e., for some .
Definition 8.12 (Low hierarchy and high hierarchy within NP) For , define the th level of the
low hierarchy in NP by ;
high hierarchy in NP by .
Informally put, a set is in if and only if it is useless as an oracle for a computation. All information contained in can be computed by the machine itself without the help of an oracle. On the other hand, a set in is so rich and provides so useful information that the computational power of a machine is increased by the maximum amount an NP set can provide: it “jumps” to the next level of the polynomial hierarchy. That is, by using an oracle from , a machine can simulate any computation. Thus, is as useful for a machine as any NPcomplete set.
For , the question of whether or not is nothing other than the PversusNP question. Theorem 8.13 lists some important properties of these hierarchies, omitting the proofs, see [ 226 ] and Exercise 82. For the class mentioned in the first item of Theorem 8.13, the reader is referred to the definition of the ArthurMerlin hierarchy introduced in Subsection 7.5.1; cf. Definition 7.16. Ladner's theorem (Theorem 8.7) is a special case (for ) of item 7 in Theorem 8.13.
1. and and .
2. .
3. .
4. .
5. .
6. For each , is nonempty if and only if .
7. For each , NP contains sets that are neither in nor in if and only if .
8. There exist sets in NP that are neither in nor in if and only if is a strictly infinite hierarchy, i.e., if and only if does not collapse to a finite level.
We now turn to the result that the graph isomorphism problem () is in , the second level of the low hierarchy. This result provides strong evidence against the NPcompleteness of , as can be seen as follows. If were NPcomplete, then would be in , since by Theorem 8.13 contains exactly the complete NP sets and in particular the complete sets in NP. Again by Theorem 8.13, we have that is nonempty if and only if collapses to , which is considered very unlikely.
To prove the lowness of the graph isomorphism problem, we first need a technical prerequisite, the socalled hashing lemma, stated here as Lemma 8.15. Hashing is method widely used in computer science for dynamic data management. The idea is the following. Assign to every data set some (short) key in a unique manner. The set of all potential keys, called the universe , is usually very large. In contrast, the set of those keys actually used is often much smaller. A hash function maps the elements of to the hash table . Hash functions are manytoone mappings. That is, distinct keys from can be mapped to the same address in . However, if possible, one wishes to map two distinct keys from to distinct addresses in . That is, one seeks to avoid collisions on the set of keys actually used. If possible, a hash function thus should be injective on .
Among the various known hashing techniques, we are here interested in universal hashing, which was introduced by Carter and Wegman [ 41 ] in 1979. The idea is to randomly choose a hash function from a suitable family of hash functions. This method is universal in the sense that it does no longer depend on a particular set of keys actually used. Rather, it seeks to avoid collisions with high probability on all sufficiently small sets . The probability here is with respect to the random choice of the hash function.
In what follows, we assume that keys are encoded as strings over the alphabet . The set of all length strings in is denoted by .
Definition 8.14 (Hashing) Let , and let and be positive integers with . A hash function is a linear mapping determined by a Boolean matrix , where . For and , the th bit of in is given by , where denotes the logical exclusiveor operation, i.e.,
Let be a family of hash functions for the parameters and :
On , we assume the uniform distribution: A hash function is chosen from by picking the bits in independently and uniformly distributed.
Let . For any subfamily of , we say there is a collision on if
Otherwise, is said to be collisionfree on .
A collision on means that none of the hash functions in a subfamily is injective on . The following lemma says that, if is sufficiently small, a randomly chosen subfamily of must be collisionfree. In contrast, if is too large, collisions cannot be avoided. The proof of Lemma 8.15 is omitted.
Lemma 8.15 (Hashing lemma) Let be fixed parameters, where . Let and let be a family of hash functions randomly chosen from under the uniform distribution. Let
be the event that for a collision occurs on . Then, the following two statements hold:
1. If , then occurs with probability at most .
2 . If , then occurs with probability .
In Section 7.5, the ArthurMerlin hierarchy has been defined, and it was mentioned that this hierarchy collapses to its second level. Here, we are interested in the class , cf. Definition 7.16 in Subsection 7.5.1.
Theorem 8.16 (Schöning) is in .
Proof. By Theorem 8.13, every set is in . Thus, to prove that in , it is enough to show that is in . Let and be two graphs with vertices each. We wish to apply Lemma 8.15. A first idea is to use
as the set from that lemma. By Lemma 7.11, we have if , and if .
The machine we wish to construct for is polynomialtime bounded. Thus, the parameters and from the hashing lemma must be polynomial in . So, to apply Lemma 7.11, we would have to choose a polynomial such that
This would guarantee that the set would be large enough to tell two isomorphic graphs and apart from two nonisomorphic graphs and . Unfortunately, it is not possible to find a polynomial that satisfies (8.4). Thus, we define a different set , which yields a gap large enough to distinguish isomorphic graphs from nonisomorphic graphs.
Define . Now, (8.4) changes to
and this inequality can be satisfied by choosing , which is polynomially in as desired.
Construct a machine for as follows. Given the graphs and each having vertices, first computes the parameter . The set contains tuples of pairs each having the form , where is a graph with vertices, and where is a permutation in the automorphism group . The elements of can be suitably encoded as strings over the alphabet , for a suitable polynomial . All computations performed so far are deterministic.
Then, performs Arthur's probabilistic move by randomly choosing a family of hash functions from under the uniform distribution. Each hash function is represented by a Boolean matrix. Thus, the hash functions in can be represented as a string of length for a suitable polynomial . Modify the collision predicate defined in the hashing lemma as follows:
Note that the quantifier in ranges over only polynomially many and can thus be evaluated in deterministic polynomial time. It follows that the two quantifiers in can be merged into a single polynomially lengthbounded quantifier. By Theorem 8.11, is a set in . Let be an NPTM for . For the string that encodes randomly picked hash functions from , now simulates the computation of . This corresponds to Merlin's move. Finally, accepts its input if and only if accepts.
We now estimate the probability (taken over the random choice of the hash functions in that accepts its input . If and isomorphic, then by Lemma 7.11. Inequality (8.5) implies . By Lemma 8.15, the probability that is in (and that thus accepts) is at most . However, if and are nonisomorphic, Lemma 7.11 implies that . Inequality (8.5) now gives . By Lemma 8.15, the probability that is in and thus accepts is . It follows that is in as desired.
The probabilistic complexity class RP was introduced in Definition 7.14 in Subsection 7.3.1. In this section, two other probabilistic complexity classes are important that we will now define: and , which stand for Probabilistic Polynomial Time and Stoic Probabilistic Polynomial Time, respectively.
Definition 8.17 (PP and SPP) The class contains exactly those problems for which there exists an NPTM such that for each input : If then accepts with probability at least , and if then accepts with probability less than .
For any NPTM running on input , let denote the number of accepting computation paths of and let denote the number of rejecting computation paths of . Define .
The class contains exactly those problems for which there exists an NPTM such that for each input : and .
In other words, an machine is “stoic” in the sense that its “gap” (i.e., the difference between its accepting and rejecting computation paths) can take on only two out of an exponential number of possible values, namely and . Unlike , is a socalled “promise class”. since an machine “promises” that for each .
The notion of lowness can be defined for any relativizable complexity class : A set is said to be low if and only if . In particular, for each , the th level of the low hierarchy within NP (see Definition 8.12) contains exactly the NP sets that are low. It is known that all sets in are low. This and other useful properties of are listed in the following theorem without proof; see also [ 71 ], [ 150 ], [ 151 ].
1. is low, i.e., .
2. is selflow, i.e., .
3. Let be a set in NP via some NPTM and let be a set in via some NPOTM such that, for each input , asks only queries satisfying . Then, is in .
4. Let be a set in NP via some NPTM and let be a function in via some DPOTM such that, for each input , asks only queries satisfying . Then, is in .
The following theorem says that the lexicographically smallest permutation in a right coset (see Definition 7.6 in Section 7.1.3) can be determined efficiently. The lexicographic order on is defined in Example 8.3.
Theorem 8.19 Let be a permutation group with and let be a permutation in . There is a polynomialtime algorithm that, given , computes the lexicographically smallest permutation in the right coset of in .
Proof. We now state our algorithm
LERC
for computing the lexicographically smallest permutation in the right coset of in , where the permutation group is given by a generator , see Definition 7.6 in Subsection 7.1.3.
LERC(
)
1 compute the tower of stabilisers in 2 3FOR
TO
4DO
5 compute the element in the orbit for which is minimum 6 compute a permutation in such that 7 8RETURN
By Theorem 7.7, the tower of stabilisers of can be computed in polynomial time. More precisely, for each with , the complete right transversals in are determined, and thus a strong generator of .
Note that and . Thus, to prove that the algorithm works correctly, it is enough to show that for each with , the lexicographically smallest permutation of is contained in . By induction, it follows that also contains the lexicographically smallest permutation of . Thus, algorithm
LERC
indeed outputs the lexicographically smallest permutation of of .
To prove the above claim, let us denote the orbit of an element in a permutation group by . Let be the permutation in that maps onto the element in the orbit for which is the minimal element in the set .
By Theorem 7.7, the orbit can be computed in polynomial time. Since contains at most elements, can be determined efficiently. Our algorithm ensures that . Since every permutation in maps each element of onto itself, and since , it follows that for each with , for each , and for each ,
In particular, it follows for the lexicographically smallest permutation in that every permutation from must coincide with on the first elements, i.e. on .
Moreover, for each and for the element defined above, we have
Clearly, . The claim now follows from the fact that for the lexicographically smallest permutation of .
Thus,
LERC
is a correct algorithm. It easy to see that it is also efficient.
Theorem 8.19 can easily be extended to Corollary 8.20, see Exercise 83.
Corollary 8.20 Let be a permutation group with , and let and be two given permutations in . There exists a polynomialtime algorithm that, given , computes the lexicographically smallest permutation of .
We now prove Theorem 8.21, the main result of this section.
Theorem 8.21 (Arvind and Kurur) is in .
Proof. Define the (functional) problem as follows: Given a graph , compute a strong generator of the automorphism group ; see Definition 7.6 and the subsequent paragraph and Definition 7.8 for these notions. By Mathon's [ 176 ] result, the problems and are Turingequivalent (see also [ 151 ]), i.e., is in and is in . Thus, it is enough to show that is in because the selflowness of stated in Theorem 8.18 implies that is in , which will complete the proof. So, our goal is to find an algorithm for . Given a graph , this algorithm has to compute a strong generator for , where
is the tower of stabilisers of and , , is a complete right transversal of in .
Starting with the trivial case, , we build step by step a strong generator for , where is decreasing. Eventually, we will thus obtain a strong generator for . So suppose a strong generator for has already been found. We now describe how to determine a complete right transversal of in by our algorithm. Define the oracle set
By Theorem 8.19, the lexicographically smallest permutation
LERC
of the right coset can be determined in polynomial time by our algorithm. The partial permutation belongs to the input , since we wish to use as an oracle in order to find the lexicographically smallest permutation by prefix search; cf. Example 8.3.
Consider the following NPTM for :
N(
)
1 verify that 2 nondeterministically guess a permutation ; has vertices 3IF
and and extends andLERC
4THEN
accept and halt 5ELSE
reject and halt
Thus, is in NP. Note that if then , for each permutation in the right coset .
We now show that if then the number of accepting computation paths of on input is either or . In general, .
Suppose is in and . If for some and , then the right coset contains exactly those permutations in that map to . Thus, the only accepting computation path of corresponds to the unique lexicographically smallest permutation
LERC
. If, on the other hand, is a strict subgroup of , then can be written as the disjoint union of right cosets of . In general, thus possesses accepting computation paths if is in , and otherwise it has no accepting computation path.
MA(
)
1 set for each , ; has vertices 2 will be a complete right transversal of in . 3 set for each , 4 set will be a strong generator for . 5FOR
DOWNTO
1 is already found at the start of the th iteration, and will now be computed. 6DO
let be the partial permutation with for each 7 For , is the nowhere defined partial permutation. 8FOR
TO
9DO
, i.e., extends by the pair with 10IF
11THEN
Construct the smallest permutation in mapping to by prefix search. 12FOR
TO
13DO
find the element not in the image of with 14 15 Now, is a total permutation in 16 now, is a complete right transversal of in 17 . 18RETURN
is a strong generator for
The above algorithm is an algorithm for . The DPOTM makes only queries to its oracle for which . Thus, for each query actually asked. By item 4 of Theorem 8.18, it follows that is in .
The claim that the output of indeed is a strong generator for can be shown by induction on . The induction base is , and of course generates .
For the induction step, assume that prior to the th iteration a strong generator for has already been found. We now show that after the th iteration the set is a strong generator for . For each with , the oracle query “ ?” checks whether there is a permutation in mapping to . By prefix search, which is performed by making suitable oracle queries to again, the lexicographically smallest permutation in with is constructed. Note that, as claimed above, only queries satisfying are made to , since is a strong generator for , so . By construction, after the th iteration, is a complete right transversal of in . It follows that is a strong generator for . Eventually, after iterations, a strong generator for is found.
From Theorem 8.21 and the first two items of Theorem 8.18, we obtain Corollary 8.22.
Corollary 8.22 is low for both and , i.e., and .
Exercises
8.41 By Definition 8.9, if and only if . Show that if and only if .
8.42 Show that the set defined in Example 8.3 is in NP. Moreover, prove that the machine defined in Example 8.3 runs in polynomial time, i.e., show that is a DPOTM.
PROBLEMS

A strong NPOTM is an NPOTM with three types of final states, i.e., the set of final states of is partitioned into (accepting states), (rejecting states), and (“don't know” states) such that the following holds: If then has at least one computation path halting in an accepting state from but no computation path halting in a rejecting state from . If then has at least one computation path halting in a rejecting state from but no computation path halting in an accepting state from . In both cases may have computation paths halting in “don't know” states from . In other words, strong NPOTMs are machines that never lie. Prove the following two assertions:
(a) if and only if there exists a strong NPOTM with .
(b) if and only if .
Hint. Look at Exercise 8.41.
Prove the assertions from Theorems 8.11 and 8.13. (Some are far from being trivial!)
83
Modification of the proofs
Modify the proof of Theorem 8.19 so as to obtain Corollary 8.20.
CHAPTER NOTES

Parts of the Chapters 7 and 8 are based on the book [ 219 ] that provides the proofs omitted here, such as those of Theorems 8.11, 8.13, and 8.18 and of Lemma 8.15, and many more details.
More background on complexity theory can be found in the books [ 112 ], [ 198 ], [ 266 ], [ 271 ]. A valuable source on the theory of NPcompleteness is still the classic [ 81 ] by Garey and Johnson. The reducibility was introduced by Cook [ 51 ], and the reducibility by Karp [ 140 ]. A deep and profound study of polynomialtime reducibilities is due to Ladner, Lynch, and Selman [ 157 ].
Exercise 81 and Problem 81 are due to Selman [ 231 ].
Dantsin et al. [ 59 ] obtained an upper bound of for the deterministic time complexity of , which was further improved by Brueggemann and Kern [ 34 ] to . The randomised algorithm presented in Subsection 8.3.2 is due to Schöning [ 228 ]; it is based on a “limited local search with restart”. For with , the algorithm by Paturi et al. [ 200 ] is slightly better than Schöning's algorithm. Iwama and Tamaki [ 131 ] combined the ideas of Schöning [ 228 ] and Paturi et al.[ 200 ] to obtain a bound of for with . For with , their algorithm is not better than that by Paturi et al. [ 200 ].
Figure 8.7 gives an overview over some algorithms for the satisfiability problem.
For a thorough, comprehensive treatment of the graph isomorphism problem the reader is referred to the book by Köbler, Schöning, and Torán [
152
], particularly under complexitytheoretic aspects. Hoffman [
115
] investigates grouptheoretic algorithms for the graph isomorphism problem and related problems.
The polynomial hierarchy was introduced by Meyer and Stockmeyer [ 178 ], [ 250 ]. In particular, Theorem 8.11 is due to them. Schöning [ 226 ] introduced the low hierarchy and the high hierarchy within NP. The results stated in Theorem 8.13 are due to him [ 226 ]. He also proved that is in , see [ 227 ]. Köbler et al. [ 150 ], [ 151 ] obtained the first lowness results of for probabilistic classes such as . These results were improved by Arvind and Kurur [ 12 ] who proved that is even in . The class generalises Valiant's class , see [ 261 ]. Socalled “promise classes” such as and have been thoroughly studied in a number of papers; see, e.g., [ 12 ], [ 30 ], [ 71 ], [ 150 ], [ 151 ], [ 210 ], [ 218 ]. Lemma 8.15 is due to Carter and Wegman [ 41 ].
The author is grateful to Uwe Schöning for his helpful comments on an earlier version of this chapter and for sending the slides of one of this talks that helped simplifying the probability analysis for the algorithm
RandomSAT
sketched in Subsection 8.3; a more comprehensive analysis can be found in Schöning's book [
229
]. Thanks are also due to Dietrich Stoyan, Robert Stoyan, Sigurd Assing, Gábor Erdélyi and Holger Spakowski for proofreading previous versions of Chapters 7 and 8. This work was supported in part by the Deutsche Forschungsgemeinschaft (DFG) under grants RO 1202/91 and RO 1202/93 and by the Alexander von Humboldt Foundation in the TransCoop program.