Edit Question - KnowledgeHub

Title Body

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 questi

Tags (comma-separated) Cancel