An order of complexity
, believed to be even 'harder' than NP
. Finding the shortest route in the traveling salesman problem
is an example of this, though it is often mistakenly believed to be in NP
(The problem "is this route route shorter than n" for some n is NP-Complete).