Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let us say that there is a NP problem that is not a complete problem. And let us assume that someone found that the problem is in fact P-complete problem.

Does this imply P=NP?

share|cite|improve this question
up vote 5 down vote accepted

If there is a problem in NP, which is proven to be not $\text{NP}$-Complete, then this implies $\text{P} \neq {NP}$.

This is because, if $\text{P} = \text{NP}$, then all (non-trivial) problems are trivially $\text{NP}$-Complete: reduce $3$-$\text{SAT}$ by solving $3$-$\text{SAT}$ as part of the reduction.

Also, when it comes to completeness, $\text{P}$-Complete and $\text{NP}$-Complete are entirely different notions. Trying to relate the two seems a bit strange. Unfortunately the term "Completness" is overloaded, and the confusion which students face is understandable.

When we talk about Completeness, we have a specific constraint on the reductions we can use, which depends on the class whose completeness we are talking about. The reductions we choose for one class need not be the same as for other classes.

Usually, we define $\text{NP}$-Completness to use polynomial time reductions. There are other definitions too, look up Karp vs Cook on the web.

Usually, $\text{P}$-Completeness uses LogSpace reductions. Polynomial time reductions make no sense to define $\text{P}$-Completness: every problem would be $\text{P}$-Complete trivially.

There are problems which have been proven to be $\text{P}$-Complete under LogSpace reductions and that has no bearing on the $\text{P} = \text{NP}$ problem.

For instance, even if we managed to show that $\text{P} = \text{NP}$, it does not mean every $\text{NP}$-Complete problem is $\text{P}$-Complete. The question of whether LogSpace = P would still need to be resolved.

share|cite|improve this answer
In the last paragraph, if P=NP, then it does mean that every P-complete problem under log-space reducibility is NP-complete under polynomial-time reducibility. I think that you meant to write the opposite: even if P=NP, it does not mean that every NP-complete problem under polynomial-time reducibility is P-complete under log-space reducibility. – Tsuyoshi Ito May 12 '12 at 3:38
@TsuyoshiIto: Right. I meant it that way. In fact a previous revision had it that way and I changed it for some reason (it does not show up though). Corrected, thanks! – Aryabhata May 12 '12 at 4:52

Let's start with very rough and informal descriptions of P and NP.

P is the set of decision problems that can be solved "quickly".

NP is the set of problems for which a proposed solution can be checked "quickly". If I tell you that $x$ is a solution to your problem, then you can quickly check whether or not $x$ really is a solution.

In particular, all problems in P are also in NP. Intuitively, it is easier to check whether $x$ is a solution than to actually find a solution. So all P-complete problems are automatically in NP. Finding a NP-problem which is P-complete is the same as finding a P-complete problem. It does not tell us anything about whether $P=NP$ or $P \neq NP$.

Thus finding a P-complete problem (like the ones on this wikipedia page) does not tell us anything about P versus NP.

share|cite|improve this answer

Your Answer


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.