14 - Circuit lower bounds & circuit-SAT

• The Cook-levin theorem states that every problem in NP can be reduced to an instance of 3-SAT
• Illustration of a general boolean circuit geometry

  A) input nodes

  B) circuit

  C) output node

  
• doubly-exponential growth of the number of boolean fucntion (in input length n)

  f : {0,1}^n -> {0,1} is exactly N(n) = 2^2^n
• THe number of distrinct size circuits with n inputs, m=1 output and size at most s is upper bounded by N(n,s) = n^(2s) (4s)^s
• Circuit lower bounds

  A) almost all

  B) exponentially large

  C) exponential

  D) 2n

  E) 6n

  
• "almost all" means that boolean functions f that have cricuits with the advertised size bound only cover a vanishingly small fractionr of all possible boolean functions.
• almost all boolean fucntions have a circuit representation that obeys

  A) 2^n

  B) 6n

  C) 2^n

  D) 2n

  
• There are n-variable Boolean functions that can be computed by circuits of size O (n^2), but cant be computed by circuits of size O (n). In formulas: SIZE (n) ⊂ SIZE(n^2) (strict inclusion)
• size hierarchy theorem

  large circuit sizes yield strictly more computing power.
• time hierachy theorem

  longer TM runtimes yield strictly more computing power
• Circuit SAT

  A) boolean

  B) satisfiable

  C) 1

  D) bit encodings

  
• Every NP-problem admits a polynomialtime reduction to an instance of circuit-SAT
• Every circuit-SAT instance andmits a linear-time reduction to an instance of 3-SAT
• 3-SAT is NP-complete, i.e. every NP-problem admits a polynomial-time reduction to an instance of 3-SAT