Do any decision problems exist outside NP and NP-Hard?

Do any decision problems exist outside NP and NP-Hard?

• http://cs.stackexchange.com/questions/9063/np-hard-that-is-not-np-complete-and-not-undecidable asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard. In order to be in NP, problems have to have a verifier that runs in polynomial time on a deterministic Turing machine. Obviously, all problems in P meet that criteria, but what about the problems with sub-exponential complexity? They do not belong to P and it's not obvious to me that they all have efficient deciders. And they certainly don't qualify for NP-complete. I'm willing to believe that all decision problems are either NP or NP-hard or both, but nobody has actually said that (that I can find). I'm also willing to believe that such problems do exist, even if they are very contrived. Maybe someone more knowledgeable can put this issue to rest for me. Thanks. Edit I abused the term 'subexponential' in my question. In my mind it meant some problem with a complexity between exponential and polynomial like L-notation in http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions. See the links in Raphael's answer for more details.

• Answer:

  NP contains all (decision) problems that are at most as hard as NP-complete problems with respect to https://en.wikipedia.org/wiki/Karp_reduction. NP-hard contains all (decision) problems that are at least as hard as NP-complete problems with respect to https://en.wikipedia.org/wiki/Karp_reduction. So, in the "Karp-reduction universe", NP and NP-hard do indeed cover everything. There may be orthogonal problem classes, though: for instance, https://en.wikipedia.org/wiki/Co_np-complete are neither in NP nor NP-hard (w.r.t. Karp reductions) if NP does not equal co-NP (which we don't know). Aside from that, note that http://cs.stackexchange.com/questions/9813/are-there-subexponential-time-algorithms-for-np-complete-problems, but no known polynomial ones. Thanks http://cs.stackexchange.com/users/6716/frafl for pointing out a critical flaw in the initial version of this answer. Readers of the old version may want to read http://cs.stackexchange.com/questions/7676.