If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?

Question

I discover this in All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

• If problem B is in P and A reduces to B, then problem A is in P.
• Problem B is NP-complete if B is in NP and for every problem in A in NP, A reduces to B.
• Problem C is NP-complete if C is in NP and for some NP-complete problem B, B reduces to C.

My questions are (if I then II then(?) III/I. If III/I and III/II then IV.)

• I: Are there a generalized form to reduces NP problem to either P or NP-complete?
• II: Are there a certain number of NP-complete problems?
• III/I: Are all of the NP-complete problems can be reduces to all other NP-problems?
• III/II: If we can reduce B in NP-complete problem to A in P, can we prove that all problem reduces to B is in P?
• IV: If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?

Answer 1

I. I was not able to parse the question, sorry.

II. There is an infinite number of NP-complete problems.

III/I. Each NP-complete problem can be reduced to any other NP-complete problem.

III/II. If you show that there exists a (Karp) reduction from a NP-complete $B$ problem to a problem in P, then you have proved that all problems that reduce to $B$ are also in P. In particular this implies NP $\subseteq$ P, and hence P=NP.

IV. If a NP-complete problem is in P, then P=NP.

Answer 2

When it comes to polynomial time reductions from $A$ to $B$, I find it useful to think of it as "Solving problem $A$ by converting it to problem $B$, then using a 'Problem $B$ Solver'."

With this in mind:

1. There are currently many NP problems that have not (yet) been shown to be in NP-Complete or P. If there truly exists NP problems that are neither in NP-Complete nor P, then this would imply P!=NP. Moreover, Ladner's Theorem tells us that the converse is true: if P!=NP, then such NP-intermediate problems exist.
2. Yes, but it may not mean what you think it means. To answer this properly, we need to look at the definitions. NP problems are decision problems, and correspond to languages, which are collections of strings representing the instances that are in the language. But there are an infinite number of representations for a given problem. For example, the PRIME problem could be represented by the collection of binary strings whose value are prime. Alternatively, we could have stored them as the collection of strings in base 10. Or base 11. Or 12...
3. Yes: the definition of an NP-Complete problem is that every NP problem (incl. NP-Complete problems) can be reduced to it.
4. Yes: To solve an NP problem in polynomial time, reduce it to the NP-Complete problem then solve it in polynomial time.