4 ms·
The goal here was to show that it was strictly NP-hard, i.e. harder than any problem in NP.
by andrewla 2y ago
The goal here was to show that it was strictly NP-hard, i.e. harder than any problem in NP.
- Nevermark 2y agoHarder to solve, not necessarily harder to verify? If I am understanding things right.
- andrewla 2y agoThe crazy thing about the definition of NP-completeness is that Cook's theorem says that all problems in NP can be reduced in polynomial time to an NP-complete problem. So if a witness to a problem can be verified in polynomial time, it is by definition in NP and can be reduced to an NP-complete problem. If I can verify a solution to this problem by finding a path in polynomial time, it is by definition in NP. The goal here was to present an example of a problem known to not be in NP.
- thaumasiotes 2y ago> The crazy thing about the definition of NP-completeness is that Cook's theorem says that all problems in NP can be reduced in polynomial time to an NP-complete problem. What were you trying to say here? Cook's theorem says that SAT is NP-complete. "All problems in NP can be reduced in polynomial time to an NP-complete problem" is just a part of the definition of NP-completeness.