1
$\begingroup$

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?

2 Answers 2

5

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.

  • 0
    @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!2012-05-12
3

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.