P/poly

Formal definition

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

:\mathsf{P/poly} = \bigcup_{c\in\mathbb{N}} \mathsf{SIZE}(n^c),

where \mathsf{SIZE}(n^c) is the set of decision problems that can be solved by circuit families having no more than n^c gates on inputs of size n.

Alternatively, \mathsf{P/poly} can be defined using Turing machines that "take advice". Such a machine has, for each n, an advice string \alpha_n, which it is allowed to use in its computation whenever the input has size n. To help visualize this equivalence, imagine that the advice for each n is a description of a Boolean circuit having n inputs, and that a Turing Machine for the language merely evaluates the given Boolean circuit on inputs of length n.

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

:M(x, \alpha_n) = 1 \Leftrightarrow x \in L

for every x \in {0, 1}^n, where on input (x, \alpha_n) the machine M runs for at most O(T(n)) steps.

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 \Sigma_2^{\mathsf P}. This result is the Karp–Lipton theorem; furthermore, NP ⊆ P/poly implies AM = MA {{citation
• If PSPACE ⊆ P/poly then \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.{{citation | author1-link = László Babai | author2-link = Lance Fortnow | author3-link = Carsten Lund | access-date = 2011-10-02 | archive-url = https://web.archive.org/web/20120331215832/http://www.cs.uchicago.edu/files/tr_authentic/TR-91-10.ps | archive-date = 2012-03-31 | url-status = dead
• If EXPTIME ⊆ P/poly then \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{{citation
• If EXP****NP ⊆ P/poly then \mathsf{EXP^{NP}} = \Sigma_2^{\mathsf P} \cap \Pi_2^{\mathsf P} (Buhrman, Homer)
• It is known that MAEXP, an exponential version of MA, is not contained in P/poly. : Proof: If MAEXP ⊆ P/poly then PSPACE = MA (see above). By padding, EXPSPACE = MAEXP, therefore EXPSPACE ⊆ P/poly but this can be proven false with diagonalization.
• The best known bound for the square-root sum problem is in the fourth level of the counting hierarchy, and it is an unsolved problem whether better complexity is possible, but a unary version of the problem is in P/poly.{{citation | editor1-last = Parter | editor1-first = Merav | editor2-last = Pettie | editor2-first = Seth

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, NPA is not a subset of PA**/poly** with probability 1.{{citation

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.

Bounded-error probabilistic polynomial is contained in P/poly

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;{{citation Variants of the theorem show that BPL is contained in L/poly and AM is contained in NP/poly.

Proof

Let L be a language in BPP, and let M(x,r) be a polynomial-time algorithm that decides L with error ≤ 1/3 (where x is the input string and r is a set of random bits).

Construct a new machine (x,R), which runs M 48n times and takes a majority vote of the results (where n is the input length and R is a sequence of 48n independently random rs). Thus, ** is also polynomial-time, and has an error probability ≤ 1/*en* by the Chernoff bound (see BPP). If we can fix R then we obtain an algorithm that is deterministic.

If \mbox{Bad}(x) is defined as {R: M(x, R) \text{ is incorrect}}, we have:

:\forall x, \mbox{Prob}_R[R \in \mbox{Bad}(x)] \leq \frac{1}{e^n}.

The input size is n, so there are 2n possible inputs. Thus, by the union bound, the probability that a random R is bad for at least one input x is

:\mbox{Prob}_R [\exists x,R \in \mbox{Bad}(x)] \leq \frac{2^n}{e^n}

In words, the probability that R is bad for at least one x is less than 1, therefore there must be an R that is good for all x. Take such an R to be the advice string in our P/poly algorithm.

References

References

1. "Lecture notes on computational complexity by Peter Bro Miltersen".
2. Caldwell, Chris. "2.3: Strong probable-primality and a practical test". Finding primes & proving primality.
3. (2009). "Computational complexity. A modern approach". [[Cambridge University Press]].
4. [http://cse.unl.edu/~cbourke/pubs/EXPnote.pdf A Note on the Karp-Lipton Collapse for the Exponential Hierarchy]
5. Jin-Yi Cai. [http://pages.cs.wisc.edu/~jyc/02-810notes/lecture11.pdf Lecture 11: P/poly, Sparse Sets, and Mahaney's Theorem]. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003.
6. Charles H. Bennett, John Gill. ''Relative to a Random Oracle A, P^A ≠ NP^A ≠ co-NP^A with probability 1''. [https://www.cs.cornell.edu/courses/cs682/2006sp/handouts/bennettgill.pdf]{{Open access