Hacker News new | past | comments | ask | show | jobs | submit login

No. The traveling salesman decision problem (is there a circuit of length m) is NP complete. The traveling salesman problem (what is the shortest circuit) is harder. This has been discussed on HN before.



All NP problems are decision problems. When you say "x is in NP", you're implicitly referring to the decision problem. NP-hard does not mean "harder than NP", although that is its colloquial interpretation.




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: