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 c开发者_如何转开发hoice, 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
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
- 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
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 inNP
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 thatNP != P
.
Qiaochu Yuan, What techniques exist to show that a problem is not NP-complete?,
might help.
精彩评论