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

Question

I have a course called Algorithm Analysis at college, where we're currently studying the different complexity classes -- P, NP, NP-hard etc.

We've already discussed NP-complete problems as the intersection between NP and NP-hard, and P problems, contained in NP. We've also talked about some examples, mainly of NP-complete problems (k-coloring, k-clique, SAT).

Most of the time, we prove a problem is NP-complete by:

a. Finding a nondeterministic algorithm to solve it (that uses choice, success, fail);

b. Reducing a known NP-complete problem to it.

The thing is that these problems, when run on a deterministic machine (sequentially, instead of simultaneously branching when encountering a choice) have exponential-time solutions.

My question is this -- I've never encountered problems that were solvable neither in polynomial time neither in exponential time; polynomial time problems are in P and exponential-time problems are usually in NP-complete.

There's a helpful Venn diagram here: http://en.wikipedia.org/wiki/Np_complete

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

2. Also, are intrinsically exponential problems, like generating the power set of a set NP-complete? Or does that name only apply for problems for which an exponential time algorithm is used only because there's no other obvious method for solving it?

Ok, so I gave the answer to Rosh Oxymoron because he actually listed some examples of problems suspected to be between P and NPC. Thanks for your help guys, and I actually noticed that I put this question in the wrong place. There's also: https://cstheory.stackexchange.com/

where I found the following very useful answers to my question: https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc which is specifically about what I asked, and: https://cstheory.stackexchange.com/questions/52/hierarchies-in-np-under-the-assumption-that-p-np which is generally interesting, if not exactly related to the initial question.

Thanks a lot,

Dan

Answer 1

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

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

Answer 2

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: http://www.claymath.org/millennium/P_vs_NP/

Answer 3

1. There is no problem known to be in NP \ NPC.

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

Answer 4

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

might help.