P/poly

In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equivalently in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial-time Turing machine with advice strings of length polynomial in the input size.^[1][2] These two different definitions make P/poly central to circuit complexity and non-uniform complexity.

For example, the popular Miller–Rabin primality test can be formulated as a P/poly algorithm: the "advice" is a list of candidate values to test. It is possible to precompute a list of ${\displaystyle O(n)}$ values such that every composite ${\displaystyle n}$-bit number will be certain to have a witness ${\displaystyle a}$ in the list.^[3] For example, to correctly determine the primality of 32-bit numbers, it is enough to test ${\displaystyle a\in \{2,7,61\}}$.^[4][5] The existence of short lists of candidate witnesses follows from the fact that for each composite ${\displaystyle n}$, three out of four candidate values successfully detect that ${\displaystyle n}$ is composite. From this, a simple counting argument similar to the one in the proof that BPP ${\displaystyle \subset }$ P/poly below shows that there exists a suitable list of candidate values for every input size, and more strongly that most long-enough lists of candidate values will work correctly, although finding a list that is guaranteed to work may be expensive.^[3]

P/poly, unlike other polynomial-time classes such as

The complexity class P/poly can be defined in terms of SIZE as follows:

${\displaystyle {\mathsf {P/poly}}=\cup _{c\in \mathbb {N} }{\mathsf {SIZE}}(n^{c}).}$

where ${\displaystyle {\mathsf {SIZE}}(n^{c})}$ is the set of decision problems that can be solved by polynomial-sized circuit families.

Alternatively, ${\displaystyle {\mathsf {P/poly}}}$ can be defined using Turing machines that "take advice". Such a machine has, for each n, an advice string ${\displaystyle \alpha _{n}}$, which it is allowed to use in its computation whenever the input has size n.

Let ${\displaystyle T,a:\mathbb {N} \rightarrow \mathbb {N} }$ be functions. The class of languages decidable by time-T(n) Turing machines with ${\displaystyle a(n)}$ advice, denoted ${\displaystyle {\mathsf {DTIME}}(T(n))/a(n)}$, contains every language L such that there exists a sequence ${\displaystyle \{\alpha _{n}\}_{n\in \mathbb {N} }}$ of strings with ${\displaystyle \alpha _{n}\in \{0,1\}^{a(n)}}$ and a TM M satisfying

${\displaystyle M(x,\alpha _{n})=1\Leftrightarrow x\in L}$

for every ${\displaystyle x\in \{0,1\}^{n}}$, where on input ${\displaystyle (x,\alpha _{n})}$ the machine M runs for at most ${\displaystyle O(T(n))}$ steps.^[6]

Importance of P/poly

P/poly is an important class for several reasons. For theoretical computer science, there are several important properties that depend on P/poly:

• If NP ⊆ P/poly then PH (the polynomial hierarchy) collapses to ${\displaystyle \Sigma _{2}^{\mathsf {P}}}$. This result is the Karp–Lipton theorem; furthermore, NP ⊆ P/poly implies AM = MA ^[7]
• If PSPACE ⊆ P/poly then ${\displaystyle {\mathsf {PSPACE}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}}$, even PSPACE = MA.

Proof: Consider a language L from PSPACE. It is known that there exists an interactive proof system for L, where actions of the prover can be carried out by a PSPACE machine. By assumption, the prover can be replaced by a polynomial-size circuit. Therefore, L has a MA protocol: Merlin sends the circuit as proof, and Arthur can simulate the IP protocol himself without any additional help.

• If P
  #P-completeness of permanent
  .
• If EXPTIME ⊆ P/poly then ${\displaystyle {\mathsf {EXPTIME}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}}$ (Meyer's theorem), even EXPTIME = MA.
• If NEXPTIME ⊆ P/poly then NEXPTIME = EXPTIME, even NEXPTIME = MA. Conversely, NEXPTIME = MA implies NEXPTIME ⊆ P/poly^[9]
• If EXP^NP ⊆ P/poly then ${\displaystyle {\mathsf {EXP^{NP}}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi _{2}^{\mathsf {P}}}$ (Buhrman, Homer) ^[10]
• It is known that MA_EXP, an exponential version of MA, is not contained in P/poly.