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 exact

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.