4 ms·
Thanks for this, and especially your other comment where you sketched the reduction. I don't entirely see how it falls out of the definition of NP like you say,
by mikeash 11y ago
Thanks for this, and especially your other comment where you sketched the reduction. I don't entirely see how it falls out of the definition of NP like you say, but your sketch makes a lot of sense for how to make it happen.
Just to make sure I got this right, the basic idea is: simulate the non-deterministic Turing machine using boolean variables, with unconstrained variables for the nondeterministic part. Sort of a symbolic execution on a Turing machine. Convert the simulation to a boolean expression. Convert the boolean expression to 3-SAT form. Put 3-SAT problem into your magical P==NP machine and get an answer out. You've now found the answer given by the nondeterministic Turing machine in polynomial time, if the original would indeed run in polynomial time.
- teraflop 11y agoNo problem! And sorry if I was being too terse. Re "how it falls out of the definition of NP", I think that was largely a failure on my part to understand exactly what you were asking about. The parts that are "by definition" are: * the set of programs involving steps like "guess magically" correspond to the ones that can be implemented with at most polynomial slowdown by a non-deterministic Turing machine (this is hand-wavy, but then again we're talking about pseudocode; it's possible to state it more precisely) * if such an algorithm runs in polynomial time, then it's in NP (by the definition of NP) * ...so it can be reduced to an instance of any NP-complete problem (by the definition of NP-complete) * ...and if P=NP then there exists a deterministic, polynomial-time algorithm to solve the problem The parts that require actual proofs are: * the fact that the "well-known" examples of NP-complete problems like 3-SAT, TSP, and so on actually correspond to the formal definition of NP. These proofs ultimately reduce to the Cook-Levin theorem, or something similar in spirit. * the fact that if any problem in NP has a deterministic polynomial-time algorithm, then there is one algorithm that can solve all NP problems in polynomial time. This relies on the existence of universal Turing machines that have at most a polynomial slowdown. It's likely there are other details that I'm forgetting, but that's the gist of the argument.
- mikeash 11y agoThanks for elaborating. I think that makes sense. I need to read it over again to make sure, but I'm getting there. And I don't think you were too terse. Thankfully HN makes it easy to see sub-replies to your comments so I saw your reply to 1arity, which was exactly what I needed, and your reply to me capped it off.