9
$\begingroup$

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?

3 Answers 3

10

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: https://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.

  • 0
    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...2011-03-14
  • 0
    @Steven: Please see my edit.2011-03-14
  • 0
    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!2011-03-14
  • 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.2011-03-14
  • 0
    The OP didn't restrict things to between P and NP. There are classes that are subsets of P which might be proper subclasses.2011-03-15
  • 0
    @Mitch: [Time Hierarchy Theorem](http://en.wikipedia.org/wiki/Time_hierarchy_theorem) guarantees such proper subclasses. I don't see your point, though. Can you please elaborate? Thanks.2011-03-15
  • 0
    @Moron: If a problem in P is shown to be NP-complete, then that shows that P=NP. But if the problem in P is -not- NP-complete, it does not follow that P != NP. Take an extreme class, the class of problems that take constant time to decide (i.e. need no resources at all to decide). This is -definitely- a subset of NP (you can easily compute these constant time decision problems using an NP TM (you can always use less than you have available). But trivially -no- problem here is NPC. ANd this is not a proof of 'P!=NP'. There are nontrivial problems that provably NPC problems do not to.2011-03-15
  • 0
    @Mitch: If P=NP, then every problem in P is NP-Complete. There is a vacuous polynomial time reduction: we solve the problem as part of the reduction... If we define NP-Completeness via Logspace reduction, then maybe what you say is possible, but I am not so sure.2011-03-15
  • 0
    @Moron:If P=NP, then every **P-complete** problem is NP-Complete. There are problems in P (and therefore NP) that provably **not** NP-complete. To amend your answer, it should be "If there is some problem that is P-complete, but it is provably not NP-Complete, it would imply that P≠NP." (and the rest of your answer though true and interesting is not saying the relevant story: there's an infinite hierarchy -beneath- P, too. (yes, as one gets smaller and smaller, one must use much more restricted reductions there, even more than logspace).2011-03-15
  • 0
    @Mitch: P-Completeness uses Logspace reductions. If you define NP-Completeness via polynomial time reductions, then P=NP implies _every_ problem in P (except possibly the trivial problem which either says yes or no for all inputs) is NP-Complete, not just the P-Complete problems. See this answer by David Eppstein: http://mathoverflow.net/questions/9221/what-techniques-exist-to-show-that-a-problem-is-not-np-complete/9226#9226.2011-03-15
  • 0
    @Moron: Given that NP-completeness is defined using PTIME reductions, I realize now that if $P=NP$ then, yes, all problems in NP would be NP-complete (except for the pedantic trivial case I mention). But I still find this an annoying technicality. The whole direction of proliferation of complexity classes is to either show that some collapse (some definitions turn out to describe the same class) or show strict inclusion, and lumping all subclasses of P together ignores the complex hierarchy there.2011-03-16
  • 0
    @Mitch: 1) I don't think it has yet been shown there are non-trivial problems in P which are not P-Complete. 2) If it so happens that P=NP after all, then I am pretty sure we would switch our definitions to logspace reductions, keeping any potential layers within P intact. So I don't see any issues there. Anyway...2011-03-16
  • 0
    @Moron: see http://cstheory.stackexchange.com/questions/5507/is-there-a-well-known-nontrivial-subset-of-np-for-which-it-is-known-that-it-is-a/5575#5575 for some discussion about this. It doesn't answer definitively the OP's questions, but it provides some basis for my perspective. Though that commentary doesn't say this, the 'yes' answer I give in my answer is true, but currently known only for the trivial problem, but highly expected to be true by analogy with the fact that P-complete problems are known to be not EXPTIME-complete. It all depends on the reduction class.2011-03-20
1

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).

0

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)