P/poly

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]

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 ⊆ P/poly then P^#P = MA.[8] The proof is similar to above, based on an interactive protocol for permanent and #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.

Proof: If MA_EXP ⊆ P/poly then PSPACE = MA (see above). By padding, EXPSPACE = MA_EXP, therefore EXPSPACE ⊆ P/poly but this can be proven false with diagonalization.

One of the most interesting reasons that P/poly is important is the property that if NP is not a subset of P/poly, then P ≠ NP. This observation was the center of many attempts to prove P ≠ NP. It is known that for a random oracle A, NP^A is not a subset of P^A/poly with probability 1.[1]

P/poly is also used in the field of cryptography. Security is often defined 'against' P/poly adversaries. Besides including most practical models of computation like BPP, this also admits the possibility that adversaries can do heavy precomputation for inputs up to a certain length, as in the construction of rainbow tables.

Although not all languages in P/poly are sparse languages, there is a polynomial-time Turing reduction from any language in P/poly to a sparse language.[11]

Adleman's theorem states that BPP ⊆ P/poly, where BPP is the set of problems solvable with randomized algorithms with two-sided error in polynomial time. A weaker result was initially proven by Leonard Adleman, namely, that RP ⊆ P/poly;[12] and this result was generalized to BPP ⊆ P/poly by Bennett and Gill.[13] Variants of the theorem show that BPL is contained in L/poly and AM is contained in NP/poly.