Wednesday, September 07, 2005

P/poly

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 {a0,a1,…} such that |an|≤nO(1) and x is in L if and only if (x,a|x|) is in A.
  • There is a family of circuits {C0,C1,…} such that |Cn|≤nO(1) and for all n and all x=x1…xn, x is in L if and only if Cn(x1,…,xn) accepts.
The equivalence comes from Ladner's proof that the circuit value problem is P-complete. Some argue that P/poly is a better notion of efficient computation than P since we allow the program size as well as the time to grow as the input grows. Techniques from Adleman show that BPP is contained in P/poly. However P/poly contains noncomputable and in fact an uncountable number of languages

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 at

3 comments:

  1. Anonymous12:40 PM, September 07, 2005

    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.

    The 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.)

    ReplyDelete
  2. Anonymous4:43 AM, September 09, 2005

    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.

    --David Molnar

    ReplyDelete
  3. Anonymous6:48 PM, September 10, 2005

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

    ReplyDelete

Subscribe to: Post Comments (Atom)