Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

No it doesn't. NP-Hard just states that it's NP-Complete + Polynomial Turing Time reducible to H.

NP-Complete just means that a correct solution can be evaluated in polynomial time by a deterministic Turing machine. It says nothing of the number of solutions that exist.



You've got this a little backwards. Being in NP means a correct solution can be checked by a deterministic TM in polynomial time. A problem is NP-hard if any problem in NP is polynomial time Turing reducible to it. NP-complete problems are those that are NP-hard and in NP (an NP-hard problem need not be NP-complete).




Consider applying for YC's Fall 2026 batch! Applications are open till July 27.

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

Search: