1
$\begingroup$

The Sipser text (3rd edition) contains a proof that 3-SAT is NP-Complete based on Boolean circuits. Part of the proof contains the remark that the reduction from the circuit to the Boolean formula can be done in polynomial time.

First question: is it correct to say that if a circuit C of polynomial size exists, then there must exist a formula $\varphi$ of polynomial size where C is satisfiable if and only if $\varphi$ is satisfiable?

Second question: is the Boolean formula $\varphi$ still of polynomial size if C is of polynomial size and C is derived from a deterministic Turing machine M? This seems to be described in the proof of the earlier theorem in Sipser where (by building C from a tableau of M) it is shown that if $\mbox{A $\in$ TIME$(t(n))$ for $t(n) \geq n$ and $n \in \mathbb{N}$}$ then A has circuit complexity $O(t^2(n))$.

$\endgroup$
1
$\begingroup$

Yes, that's correct. See the Tseitin transform, which describes how. It doesn't matter how the circuit $C$ was constructed.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Many thanks, D.W. ! $\endgroup$ – ShyPerson Feb 28 at 4:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.