Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] P/poly

Expand Messages
  • Lance
    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
    Message 1 of 1 , Sep 7, 2005
    • 0 Attachment
      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 Lance to Computational Complexity at 9/07/2005 10:45:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.