News for hackers. Stuff that matters.
Re:An Argument for P=NP (2005) [pdf] by teraflop on Monday August 17, 2015 @04:03PM (#10075719)
No 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.

Re:An Argument for P=NP (2005) [pdf] by mikeash on Monday August 17, 2015 @05:01PM (#10076086)
Thanks 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.