13 - Circuit size-bounded computations

• PSIZE is the complexity class which encompasses all decision problems that can be solved by circuit families of polynomial size.
• PSIZE contains problems that are uncomputable in the TM model
• a single TM works for all input sizes == unifrom model of computation
• Palindrome in Size(N)

  
• Every language A in {0,1}* is contained in size (n2^n)
• The problem class PSIZE contains all languages that can be decided using polynomial-size circuit families
• The unary halting problem is in PSIZE

  
• A circuit of familiy C is P-uniform if there exists a polynomial runimte TM which takes 1^n as input and output a descirption of the circuit.
• A language A has P-uniform circuits if and only if A in P
• The problem class P/poly if membership can eb decided by a polynomial-time TM that also ahs access to a single, polynomially bounded advice string .
• A langauge is unaray if it is a subset of {1^n : n in N}
• A language A is in P/poly if and only if it is also in PSIZE
• machine learning can be modeled as computation with advice
• Machine learning as a polynomial-runtime algorithm that takes advice.

  A) training stage

  B) prediction stage

  
• Relationship between P/poly and NP

  1. the certificate of NP-membership y depends on the acutal input x. Different length-n inputs. Suggesting that NP certificates can be more epxressive than P/poly advice string
  2. langagues A in NP are always computable. P/poly seems less restrictive than NP
• Karp-Lipton Theorem

  If NP in PSIZE then the polynomial hierarchy collapss to the second level $PH =$$\sum^P_2$
• no small circuits for SAT solving
• P = NP 0th level collapse

  NP = co-NP 1th level collapse

  NP in PSIDE 2nd level collapse
• $\Pi_2^P$


  lanague Pi 2 Sat
• The Karp-Lipton Theorem highlights that SAT is probably even harder than one has initially thought. Don't use SAT reductions too liberally