3 ms·
That's a good idea, but it won't work for a non-constructive proof.
by lisper 8y ago
That's a good idea, but it won't work for a non-constructive proof.
- kelnage 8y agoNor would it necessarily work (quickly) if the order of magnitude for any constants were sufficiently large (after all, a runtime of 2 * N and a runtime of (2^512) * N are both O(N)). If I remember correctly, in the semi-regular survey conducted with CS experts about this question, the most likely explanation that accompanied a response saying they believed that it may be the case that P=NP was “...but with very large constants”.
- erichocean 8y agoI personally distrust all non-constructive proofs as a matter of principle, and can't think of a single one I would actually miss in practice, let alone one I find convincing. They all smack of begging the question to me. I especially distrust non-constructive proofs that involve first constructing objects in an impossible manner (like, say, sorting an infinite set of infinitely long bit strings—I'm looking at you, Cantor)—and then (ab-)using the reader's intuition about actual things you can construct to "prove" nonsense about things you clearly can't. Which is a long way of saying that I'll only accept a constructive proof that P != NP (or vice versa).
- deleted 8y ago[deleted]