4 ms·
> First, that there's something inherently different about NP-complete problems, and the proof would tell us exactly what. The way I see it NP problems require
by tgflynn 6y ago
> First, that there's something inherently different about NP-complete problems, and the proof would tell us exactly what.
The way I see it NP problems require exponential time by default. The reason some of them can be solved in polynomial time is because those problems contain some special structure that allows you to short-circuit the general solution with some kind of "trick".
Then P vs. NP boils down to does there exist a "general trick". In other words do all NP problems contain structure that can be exploited to short-circuit the calculation or not.
I do agree that actually proving that P != NP seems like it would require discovering some as yet unknown structure behind virtually all of mathematics, simply because the hypothetical "general trick" could be hidden in just about any mathematical structure we know about (or even in one we haven't discovered yet).
- teraflop 6y ago> In other words do all NP problems contain structure that can be exploited to short-circuit the calculation or not. And we can strengthen this statement a bit, to really hammer home the intuition of why P=NP would be such a radical discovery. "Simulating an arbitrary non-deterministic Turing machine for K steps" is itself an NP-complete problem, which would be solvable by a polynomial algorithm if P=NP. In other words, it's not just that all NP problems would have some structure that a sufficiently clever programmer could exploit; it's that there would exist a single algorithm that could automatically discover and exploit such structure in any NP problem.
- tgflynn 6y agoYes you only need to find exploitable structure in one NP-complete problem to solve all of NP, which is why I called such a hypothetical discovery a "general trick".