4
$\begingroup$

I am not talking about NP-indeterminate class because those problems have to be shown to not exist either in P or NP-complete class and existence of such problems proves P!=NP. I am interested to know if we are half-way there i.e. problems that have been proven to be not NP-complete but are in NP but we don't know if they are in P as well.

What about such problems whose deterministic polynomial solution was found only recently? Was primality testing such a problem?

I would appreciate if the answers are given for someone like me who only has a high level understanding of computational complexity theory.

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Integer Factorization is suspected to be not NP-Hard (and not P as well) - but not proof yet. $\endgroup$ – amit Oct 17 '12 at 19:41
9
$\begingroup$

Any problem that is provably not $\mathsf{NP}$ complete (w.r.t. polynomial time reductions) would mean that the class of problems reducible to it are distinct from $\mathsf{NP}$. In other words if you show some problem is in $\mathsf{NP}$ but is not $\mathsf{NP}$ complete would imply that $\mathsf{P}$ is not equal to $\mathsf{NP}$.

In short, there is no problem in $\mathsf{NP}$ that we know it is not $\mathsf{NP}$-complete.

Regarding primality and AKS algorithm for it:

Note that the according to the current state of knowledge, it is possible that primality is NP-complete. Existence of a deterministic polynomial time algorithm for a problem does not rule out the possibility of the problem being $\mathsf{NP}$-complete.

You are probably interested in the list of problems that are conjectured to be between $\mathsf{P}$ and $\mathsf{NP}$ (known as $\mathsf{NP}$-intermediate) in which case you can check the answers to Problems Between P and NPC.

Improve this answer
$\endgroup$
  • $\begingroup$ This is not right since integer factorization is in NP but is suspected to be outside of NP complete. $\endgroup$ – argentage Oct 17 '12 at 20:16
  • 3
    $\begingroup$ @airza, what I have written is correct. Suspected is not equal to proven. The OP is asking if there is any problem that is proven not to be NP-complete and there is no such problem and will not be as long as we have not proven P is not equal to NP. $\endgroup$ – Kaveh Oct 17 '12 at 20:19
  • $\begingroup$ @ Kaveh Thanks for the answer. Could you please explain yourself here: "Existence of a deterministic polynomial time algorithm for a problem does not rule out the possibility of the problem being 𝖭𝖯-complete". I thought that if a deterministic polynomial time algorithm exists for a problem then it is in P. $\endgroup$ – Shimano Oct 18 '12 at 7:52
  • 2
    $\begingroup$ Yes, that's correct, but it's mot known that P and NP-complete are disjoint sets. For example, if P=NP then all (non-trivial) problems in P are NP-complete. $\endgroup$ – Kaveh Oct 18 '12 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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