Example problems not in P nor in NP-complete but in NP
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
I'd like to know an example of a problem that is neither in P, neither in NP-complete, but in NP.
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
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