3 ms·

What's the reduction from 3-SAT to "guessing correctly"?

• teraflop 11y ago
  The original reduction was given by the well-known Cook-Levin theorem. It's really the existence of this theorem that motivated the entire study of NP-complete problems in the first place. Basically, you can unroll the execution of a non-deterministic Turing machine along the time axis, using separate variables to represent the state of the machine at each time step. All of the rules that govern the Turing machine's execution can be encoded as Boolean formulas, resulting in one giant formula such that the formula is satisfiable iff there is an assignment of variables corresponding to a valid execution. Adding non-determinism (the "guessing") is easy; you just leave particular variables unconstrained. If the original machine runs in polynomial time, then the number of variables and clauses is also polynomial. And of course there's a straightforward polynomial reduction from SAT to 3-SAT. No offense, but if you don't already know about this, it's kind of ironic that you're the one claiming CS researchers are "arrogant" for their beliefs about P=?NP.