Hacker Newsnew | comments | show | ask | jobs | submit login

Wikipedia disagrees: http://en.wikipedia.org/wiki/NP-intermediate

"In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate"

"Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, however this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property."




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: