4
$\begingroup$

The Cook Levin theorem proves SAT is NP-Complete, but it is fairly complicated, non-constructive and uses a Turing machine.

I am confused as to why just the Tseytin Transformation does not imply/prove CNF-SAT and 3-SAT are NP-Complete.

The Tseytin transformation can transform any Circuit into a CNF-SAT which then can be transformed into a 3-SAT with only a linear amount of operations. Isn't this itself sufficient for a proof?

Doesn't every NP problem (stored on a computer) already exist somewhere as a circuit in Machine Language? And even if we don't have access to it, couldn't we transform the problem into a circuit in polynomial time? For example, the TSP would just need a polynomial amount of adders, or prime factorization would just need multipliers, etc.

What am I missing?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ Why do you say the Cook-Levin theorem is non-constructive? It seems constructive to me. $\endgroup$
    – D.W. ♦
    Commented Aug 5 at 2:56
  • $\begingroup$ You'd still need to provide a reduction (which works for all inputs) from a poly-time non-deterministic TM to a circuit SAT problem before you can apply the Tseitin transformation. Sounds like an unnecessary extra step. $\endgroup$
    – rus9384
    Commented Aug 5 at 12:41

1 Answer 1

Reset to default
9
$\begingroup$

NP-complete is defined with respect to Turing machines, not circuits.

NP-complete specified in terms of polynomial-time algorithms, where polynomial-time algorithms are formalized as Turing machines whose worst-case running time is polynomial. The Tseytin transform doesn't apply directly to Turing machines.

You can try to define an analogue of NP, but for circuits instead of Turing machines. Unfortunately, this runs into some technical problems. In particular, a circuit can only handle a fixed-size input, which means there is no notion of asymptotic running time for a circuit. In contrast, a Turing machine can handle arbitrary-size inputs, and thus we can talk about asymptotic running time (such as polynomial-time). One can try to address this with a family of circuits, but this introduces its own technical challenges. The end result is that we end up with a different complexity class, NP/poly. The question of whether P =? NP is a question about algorithms/Turing machines. There is an analogous questions for circuit complexity classes, namely, P/poly =? NP/poly, but at a technical/mathematical level, it is a different question that might possibly have a different answer.

You can think of the Cook-Levin theorem as like an analogue of the Tseytin transform. The Tseytin transform converts a circuit to a SAT instance. The Cook-Levin theorem converts a Turing machine to a SAT instance. Boolean circuits are "closer to" (more "similar to") boolean formulas than Turing machines are, and consequently the Tseytin transform looks simpler than the Cook-Levin theorem.

To learn more, see https://en.wikipedia.org/wiki/Advice_(complexity), https://en.wikipedia.org/wiki/NP/poly, https://en.wikipedia.org/wiki/P/poly, https://en.wikipedia.org/wiki/Circuit_complexity.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks so much for the clear and detailed answer! I was confused because most of the NP problems I think of such as Sudoku and Prime Factorization can be easily represented as a Boolean combinatoric Circuit (In I believe polynomial time). I now understand why you need a Turing machine to prove a problem is in NP. However, now I am curious, are there NP problems that have sequential logic/memory and can not even be represented on a Boolean combinatoric circuit? If so, could you please give an example? $\endgroup$
    – G.W.
    Commented Aug 5 at 18:24
  • 1
    $\begingroup$ Thanks, @G.W. For future reference, we'd prefer that you ask new questions via the 'Ask Question' button. The short answer is that the Cook-Levin theorem can be used to express any algorithm for a NP problem as a Boolean circuit: simply convert it to a SAT instance, then notice that the SAT instance is already a Boolean formula, which can be trivially computed by a Boolean circuit. $\endgroup$
    – D.W. ♦
    Commented Aug 5 at 21:27
  • $\begingroup$ @G.W. To prove that a problem is in NP you actually don't need circuits, but just a way to present an answer in an easily readable way (meaning it can be read in polynomial time). The harder part is the NP-hardness, which is what the main part of the Cook-Levin theorem is about. $\endgroup$
    – rus9384
    Commented Aug 5 at 21:36
  • 1
    $\begingroup$ @D.W. Oh yes, Understood, and I now realize the answer to my follow up question was obvious. But I was once again confused, because when you use the Tseytin transform on a circuit, the variables for the SAT instance can all still be seen as just 1 ands 0s of some finite initial input. I wasn't thinking how the Cook Levin theorem creates a SAT instance with variables that are true/false questions about the Turing Machine (and thus whether the original problem has sequential logic is irrelevant). This all makes sense now. Thanks Again! $\endgroup$
    – G.W.
    Commented Aug 6 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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