A student asked me why P/poly was an interesting class? A very interesting class with a funny name. It combines time and program-size complexity, and characterizes non-uniform efficient time and languages with small circuit complexity. 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.

--

Posted by Lance to Computational Complexity at 9/07/2005 10:45:00 AM- A language L is in P/poly if there is a language A in P and a set
of advice strings {a