Questions about advice and nonuniformity

An advice string is an extra input to a Turing machine which is allowed to depend on the length $n$ of the input, but not on input itself. Turing machines can simulate families of Boolean circuits if they take an advice string of proper length.

The complexity class ${\sf C}/f(n)$ denotes the class of problems decidable by Turing machines in class $\sf C$ which take advices of length $f(n)$, where $n$ is the size of input. Examples include ${\sf P}/poly$ and ${\sf NP}/poly$ (incidentally, ${\sf P}/poly$ denotes the class of languages decidable by polynomial-size circuits). Such classes are also called non-uniform because the advice strings can be supplied separately for each length without specifying how they are computed. If each advice string can itself be generated by supplying $1^n$ to an efficient circuit, then the class is called "uniform". So $\mathsf{P}$ can be thought of as $\mathsf{P}\text{poly}$ with uniform circuits

It is well-known that ${\sf BPP} \subset {\sf P}/poly$, but the inverse does not hold, since ${\sf P}/poly$ includes undecidable problems. Interestingly, even ${\sf P}/1$ (a polynomial-time Turing machine which takes one bit of advice) includes undecidable problems.

Related tags: , , , , ,


  1. Wikipedia's topic on Advice.
  2. Wikipedia's topic on Circuit Complexity
history | excerpt history