Here are two equivalent definitions of P/poly.

- A language L is in P/poly if there is a language A in P and a set
of advice strings {a
_{0},a_{1},…} such that |a_{n}|≤n^{O(1)}and x is in L if and only if (x,a_{|x|}) is in A. - There is a family of circuits
{C
_{0},C_{1},…} such that |C_{n}|≤n^{O(1)}and for all n and all x=x_{1}…x_{n}, x is in L if and only if C_{n}(x_{1},…,x_{n}) accepts.

Here are just a few areas where P/poly plays a crucial role.

**Combinatorial Approach to P versus NP**: Karp and Lipton show that if NP is in P/poly then the polynomial-time hierarchy collapses. So one approach popular in the 80's to show P≠NP tried to show an NP problem did not have polynomial-size circuits. Razborov shows the clique problem did not have polynomial-size*monotone*circuits.**Derandomization**: Nisan and Wigderson show that hardness against nonuniform classes can give us pseudorandom-number generators. Building on their work, Babai, Fortnow, Nisan and Wigderson show that if EXP is not in P/poly then BPP can be simulated in subexponential time on infinitely many input lengths.**Cryptography**: Often security is defined against P/poly adversaries to capture extraneous information in the system.**Learning Theory**: Learning polynomial circuits would be the Mecca of learning theory. Can't be done in the usual models unless factoring is easy. Bshouty et. al. show we can learn circuits probabilistically with an NP-oracle and hypothesis queries.

Even this discussion seems a bit too narrow. The real issue is the general issue of uniformity vs non-uniformity in computation and non-uniform computattion is of very substantial interest.

ReplyDeleteThe second definition in terms of circuits is extremely natural. There are many other natural non-uniform classes such as non-uniform L defined by branching programs instead of circuits.

A better name for P/poly might be "non-uniform P" (maybe a notation P/) and we should reserve the awkward P/f(n) notation for cases when f(n) is a proper sub-class of polynomials. (Unless the advice string is random access, then P/exp would be the same class.)

It is worh noting that the "extra information in the system" in the cryptographic application of P/poly has some unexpected consequences. For example, it is intuitive that zero-knowledge proofs should be closed under sequential composition...yet we only know how to prove it for P/poly adversaries (as far as I know). The use of P/poly adversaries (and simulators) also explains some of the work cryptographers must do in their definitions that may seem strange at first glance - you have to avoid things like adversaries that have keys "hard-wired" into them.

ReplyDelete--David Molnar

the random access P/exp expressed above isn't very interesting - it contains every language.

ReplyDelete