
## 5.2 Non-Uniform Complexity Classes

In the next section we make use of so-called *non-uniform complexity classes*, which are defined using *advice-taking machines*, in order to prove the impossibility of a compilation scheme. An advice-taking Turing machine is a Turing machine with an **advice oracle**, which is a (not necessarily recursive) function a from positive integers to bit strings. On input I , the machine loads the bit string a jjI jj and then continues as usual. Note that the oracle derives its bit string only from the length of the input and not from the contents of the input. An advice is said to be **polynomial** if the oracle string is polynomially bounded by the instance size. Further, if X is a complexity class defined in terms of resource-bounded machines, e.g., P or NP, then X=poly (also called **non-uniform**
X) is the class of problems that can be decided on machines with the same resource bounds and polynomial advice.

Because of the advice oracle, the class P/poly appears to be much more powerful than P. However, it seems unlikely that P/poly contains all of NP. In fact, one can prove that NP  P=poly implies certain relationships between uniform complexity classes that are believed to be very unlikely. For stating this result, we first have to introduce the *polynomial hierarchy*.

Let X be a class of decision problems. Then PXdenotes the class of decision problems P
that can be decided in polynomial time by a deterministic Turing machine that is allowed to use a procedure—a so-called **oracle**—for deciding a problem Q X, whereby executing the procedure does only cost constant time. Similarly, NPXdenotes the class of decision problems P such that there is a nondeterministic Turing-machine that solves all instances of P in polynomial time using an oracle for Q X. Based on these notions, the sets p k

,p k

, and p k are defined as follows:9

$$\begin{array}{c c c c}{{}}&{{p}}&{{}}&{{p}}&{{}}\\ {{}}&{{0}}&{{}}&{{0}}&{{}}\\ {{}}&{{p}}&{{}}&{{\mathsf{P}^{\Sigma_{k}^{p}},}}\\ {{}}&{{k+1}}&{{}}&{{}}\\ {{}}&{{p}}&{{}}&{{\mathsf{N P}^{\Sigma_{k}^{p}},}}\\ {{}}&{{k+1}}&{{}}&{{}}\\ {{}}&{{p}}&{{}}&{{}}\\ {{}}&{{k+1}}&{{}}&{{}}\end{array}$$

Thus, p 1 NP and p 1 coNP. The set of all classes defined in this way is called the polynomial hierarchy, denoted by PH. Note that

$$\mathsf{P H}$$

p p p k  PSPACE: k k k0 k0 k0

```
Further we have, p
                  k  p
                        k
                         
                             p
                              
                             k and p
                                     k
                                      
                                      ;
                                       p
                                         k  k+1. As with other classes, it is unknown whether

```

the inclusions between the classes are proper. However, it is strongly believed that this is the case, i.e., that the hierarchy is truly infinite.

Based on the firm belief that the polynomial hierarchy is proper, the above mentioned question of whether NP  P=poly can be answered. It has been shown that NP  P=poly would imply that the *polynomial hierarchy* collapses on the second level (Karp & Lipton, 1982), i.e., p 2 p 2. This, however, is considered to be quite unlikely. Further, it has been shown that NP  coNP=poly or coNP  NP=poly implies that the polynomial hierarchy collapses at the third level (Yap, 1983),
i.e., p 3 p 3, which again is considered to be very unlikely. We will use these result for proving that for some pairs of formalisms it is very unlikely that one formalism can be compiled into the other one.