Re:My survey article on P vs. NP (2017)
by teraflop on Tuesday March 23, 2021 @12:36PM
(#26556979)
> 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.
Re:My survey article on P vs. NP (2017)
by tgflynn on Tuesday March 23, 2021 @12:48PM
(#26557125)
Yes 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".
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.