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

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 Summer 2026 batch! Applications are open till May 4

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

Search: