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

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

Answer 2

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