Example problems not in P nor in NP-complete but in NP

There is no problem known to be in NP \ NPC.
A problem is in NP if and only if a non-deterministic turing machine can solve it in polynomial time (or, equivalently, a deterministic turing machine can decide it in polynomial time). This is not the case for your example.

Further it should be pointed out that we do not know whether P = NP, so it's perfectly possible (if highly unlikely) that all problems in NP can be solved in polynomial time. So if we know that a problem can not be solved in polynomial time, that problem is either not in NP or, if we can prove that it is indeed in NP, we just showed that NP != P.

Qiaochu Yuan, What techniques exist to show that a problem is not NP-complete?,

might help.

BQP problems such as integer factorization and discrete logarithm (cracking RSA and DSA) are thought to be outside of P and are also suspected to be in NP but not in NP-complete. Integer factorization is known to be in NP, and is supposed to be outside of P and NP-complete.

http://en.wikipedia.org/wiki/BQP

http://en.wikipedia.org/wiki/Integer_factorization

NP is a subset of EXPTIME, but it is expected that NP != EXPTIME (that is, EXPTIME-complete problems are not in NP). Like with P = NP, this is not yet proven (but it is known that P != EXPTIME). For example checking if an algorithm would half after k steps is EXPTIME-complete. Finding the power set is too (obviously).

http://en.wikipedia.org/wiki/EXPTIME

I'd like to know an example of a problem that is neither in P, neither in NP-complete, but in NP.

Me too; if you find one go ahead and visit this web page to claim your $1M prize: https://www.claymath.org/millennium-problems/p-vs-np-problem

Related