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

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."




Applications are open for YC Summer 2015

Guidelines | FAQ | Support | API | Lists | Bookmarklet | DMCA | Y Combinator | Apply | Contact

Search: