0

Why is the circuit for a 3-SAT instance not polynomial in size?

That is, when I am converting a SAT formula into a circuit, isn't the size of the circuit polynomial, as I have polynomial number of clauses?

user134037
  • 1
  • 1
    You appear to be confusing a circuit for a formula with a circuit for SAT. You are correct that a formula in 3-CNF can be converted to a circuit with polynomial size. But to show that 3-SAT is in P/poly, we must find a family of circuits which take a circuit as input (or more precisely, a binary encoding of a formula in 3-CNF) and output whether it is satisfiable.

    A circuit for a formula is not the same as a circuit for satisfiability.

     – Max Mar 08 '14 at 22:06
  • Thanks! That was exactly what I was confused about. – user134037 Mar 08 '14 at 22:48

0 Answers0