Wikipedia disagrees: http://en.wikipedia.org/wiki/NP-intermediate http://en.wikipedia.org/wiki/NP-intermediate "In computational complexity, problems that are

Wikipedia disagrees: http://en.wikipedia.org/wiki/NP-intermediate 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."