new | show | ask | jobs Github

Choco31415 6 months ago

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

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

▲

andrewla 6 months ago | parent [-]

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

▲

Nevermark 6 months ago | parent [-]

Harder to solve, not necessarily harder to verify?

If I am understanding things right.

▲

andrewla 6 months ago | parent [-]

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 6 months ago \| parent [-]
		> 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.