4 ms·

A sequence is easy to verify. Choosing the sequence not so much. Roughly put that is the certificate definition of being in NP.

• andrewla 1y ago
  The goal here was to show that it was strictly NP-hard, i.e. harder than any problem in NP.
  • Nevermark 1y ago
    Harder to solve, not necessarily harder to verify? If I am understanding things right.
    • andrewla 1y 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. 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 1y 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.