Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there any problem which is in NP but not in NP-Complete?

Is there any possibility that this problem is analogous to P=NP problem, if so is there any problem which is in NP, but currently there is no proof or disproof about its NP-Completeness?

share|improve this question

3 Answers 3

up vote 10 down vote accepted

If there is some non-trivial* problem in $\text{NP}$, but it is not $\text{NP}$-Complete, it would imply that $\text{P} \neq \text{NP}$. This is because if $\text{P} = \text{NP}$, then every non-trivial problem in $\text{P}$ (and so by assumption, in $\text{NP}$) is $\text{NP}$-Complete, by a polynomial time reduction which solves the problem as part of the reduction, and creates dummy input to the target problem (this is where we need the non-trivial assumption).

A classic example of a problem in $\text{NP}$, which is conjectured not to be in $\text{P}$ and not $\text{NP}$-Complete is the Graph Isomorphism Problem.

In fact, under the assumption that $\text{P} \neq \text{NP}$, it has already been proven that there are an infinite number of hierarchies in $\text{NP}$: i.e. starting with $\text{P}$ the problems becoming increasingly harder (i.e. proper subset), ending with the $\text{NP}$-Complete problems. See this cstheory question: http://cstheory.stackexchange.com/questions/52/hierarchies-in-np-under-the-assumption-that-p-np

*non-trivial means here: any language other than the empty set or it's complement.

share|improve this answer
    
A better variant might be 'under the assumption that P$\neq$NP, are any (natural) problems known to be intermediate?'; for instance, the Wikipedia article points out that GI is known not to be NP-complete under reasonable assumptions (the non-collapse of PH), but AFAIK it could be in P with no severe consequences even if P$\neq$NP... –  Steven Stadnicki Mar 14 '11 at 21:54
    
@Steven: Please see my edit. –  Aryabhata Mar 14 '11 at 22:05
    
I've seen that structural result before; that was, in fact, the genesis of my parenthetical 'natural'. GI is the closest thing I know to a natural intermediate problem, and as I noted even its intermediacy isn't guaranteed by any reasonable assumptions I'm aware of. I'd love to know of any others! –  Steven Stadnicki Mar 14 '11 at 22:11
1  
@Steven: Integer factorization is another natural problem. Not sure about it's intermediacy... I am not aware of any 'natural' problems which are known to be intermediate under P != NP. Perhaps a search on cstheory might reveal something. –  Aryabhata Mar 14 '11 at 22:15
    
The OP didn't restrict things to between P and NP. There are classes that are subsets of P which might be proper subclasses. –  Mitch Mar 15 '11 at 1:59

The class of NP problems contain all the problems in P as well. In fact, NP-complete problems are the hardest problem of the class NP. In addition, there are problems that are not known to be NP-complete (no proof yet) while we don't know any polynomial solution for them (yet).

share|improve this answer

Yes.

There's a whole lattice of complexity classes under NP, most of the ones defined by name are not known but highly suspected to be proper subsets of NP, most famously P. That is, it is not known if any particular problem in P is not NP-complete (though this is expected).

But P is not the only subclass of NP. There are the classes NL, L, AC_n, NC_n, LOGCFL, DET, etc. presumably much smaller than NP. (see the Complexity Zoo for class descriptions). There's lots of open problems about proper inclusion here.

But it turns out that NLTIME, a very restricted class, the class of problems solvable in nondeterministic log -time- (not in the Complexity Zoo)), is -provably- a proper subset of NP. That is, there are problems in NP that provably cannot be reduced to a problem in NLTIME.

The following loose inclusion order is known:

$$NLTIME \subseteq L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$$

Notice that NLTIME is a subset of NP. The only known proper inclusions in this particular list are between NLTIME and NP, and between L and PSPACE. But no one (yet) knows where (or if) there's an adjacent break in this particular linear order.

But the real question you are asking is not about complexity classes but about problems. THere are many real world problems that have complexity class analogs in the 'Zoo' (e.g. Reachability in undirected graphs is in NL). I can't seem to find a reference for the class NLTIME (it is easily definable by NTIME($\log(n)$) ), much less a given problem for it. Without thinking too hard, Im guessing some kind of decision version of Binary Search would fit.

(as an aside, there very well may be other more prominent classes, like $AC_0$, having well known problems, that are known to be properly included in NP, but I just happen not to know)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.