Hacker News Reader

A sequence is easy to verify. Choosing the sequence not so much.

Roughly put that is the certificate definition of being in NP.

The goal here was to show that it was strictly NP-hard, i.e. harder than any problem in NP.

Harder to solve, not necessarily harder to verify?

If I am understanding things right.

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.

> 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.

Reply on news.ycombinator.com