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

The NP-complete problems are a subset of NP ("nondeterministic polynomial") problems, specifically those to which all NP problems are polynomial-time reducible. They are, in essence, the hardest problems in class NP. It's pretty trivial to show that integer factoring is in NP; what's not known is whether it's NP-complete. If any NP-complete problem is in P, then via polynomial-time reduction, all problems in NP are in P.


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

Search: