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

Yes, "NP-complete" is not correct on the author's part and neither is "NP-hard." "NP-hard" is the author's intent since the problem is solvable using a SAT solver but presumably has no polynomial algorithm (so it is harder than P but not as hard as NP), but NP-hardness actually requires the other direction to be true: for a problem to be NP-hard, an oracle for the problem needs to be able to solve everything in NP. NP-complete is a stricter condition that requires NP-hardness but also requires that the problem be in NP.

The author was missing the words "in NP" if they are talking about complexity.



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

Search: