6
$\begingroup$

To prove a decision problem $C$ is in NP-complete, 2 things need to be shown:

  1. There is a polynomial verification for $C$ solution.
  2. Every problem in NP is reducible to $C$ - You can solve all the NP-complete problems in polynomial time by converting them to $C$.

To prove section 2, it is enough to show reduction of one NP-Complete problem $S$ to $C$, because we already proved that every problem in NP is reducible to $S$ by definition.

Lets assume we proved both of the conditions for $C$, and now somebody proved that $S$ belongs to P and he is claiming that $P=NP$.

I have a problem with that claim. We did proved that every problem in NP is reducible to $C$, but we did not proved that $C$ is reducible to every problem in NP, or what is interesting in our case particularly - We did not proved that $C$ is reducible to $S$.

Please prove/explain to me that claim, why we do not have to proved that $C$ is reducible to $S$ to show that $P=NP$ if $S$ belongs to $P$.

$\endgroup$
2
  • 1
    $\begingroup$ “... because we already proved that every problem in NP is reducible to $S$ by definition.” $\endgroup$
    – Carsten S
    Dec 3, 2013 at 8:49
  • $\begingroup$ some of this confusion can be cleared up by studying the original 1971 Cook (+Levin) proof of SAT as the first NP complete problem. $\endgroup$
    – vzn
    Dec 5, 2013 at 17:15

2 Answers 2

6
$\begingroup$

My understanding of your first paragraph.

To prove a decision problem $C$ [is NP-complete], 2 things need to be shown:

  1. There is a [polynomial-time] verification for [$C$'s] solution.

It requires a polynomial-time verification, for the proof of $C$'s solution, as $C$'s "solution" is simply a yes/no. The proof of the decision is essentially the solution to the equivalent optimization problem. If we can verify that the optimization problem's solution is correct in polynomial time, then this condition is satisfied.

To prove a decision problem $C$ is in NP-complete, 2 things need to be shown:

  1. There is a polynomial verification for $C$ solution.
  2. Every problem in [NP][2] is reducible to $C$ - You can solve all the NP-complete problems in polynomial time by converting them to $C$.

Think about what these conditions mean.

  1. "There is a polynomial verification for $C$ solution." - This by itself, means the problem is in $\rm NP$.
  2. "You can solve all the NP-complete problems in polynomial time by converting them to $C$" - this by itself, means the problem is $\rm NP\text{-}hard$; because if you can solve the $\rm NPC$ ($\rm NP\text{-}complete$) problems with this problem, then $\rm NPC$ problems are at most as hard as $C$, and thus $C$ is at least as hard as the $\rm NPC$ problems, and this is the definition of $\rm NP\text{-}hard$.

In my previous response, I explained the nature of these complexity classes; if something is in $\rm NP$ and $\rm NP\text{-}hard$ then it is $\rm NPC$. Here is that nice figure again, so you can see it visually (I'll leave the non-visual explicit proof to you this time):

enter image description here

(bold mine)

I have a problem with that claim. We did proved that every problem in $\rm NP$ is reducible to $C$, but we did not proved that $C$ is reducible to every problem in $\rm \mathbf{NP}$, or what is interesting in our case particularly - We did not proved that $C$ is reducible to $S$.

I think you are mixing up terminology here; I think what you mean is "to every $\rm \mathbf{NP\text{-}complete}$ problem." If this is indeed what you meant, you need to carefully think before you write things like this; think of how confusing a terminology mixup is to someone reading your question.

(bold mine)

I have a problem with that claim. We did proved that every problem in $\rm NP$ is reducible to $C$, but we did not proved that $C$ is reducible to every [$\rm NP\text{-}complete$ problem], or what is interesting in our case particularly - We did not proved that $C$ is reducible to $S$.

By virtue of being the hardest problems in $\rm NP$, any problem in $\rm NP$ can be expressed as a $\rm NP\text{-}complete$ problem; the easiest/most natural reductions are usually to $\rm k\text{-}S{\small AT}$ or $\rm C{\small IRCUIT}\text{-}S{\small AT}$, and from there you can go to any $\rm NPC$ problem.

Thus, if there is a deterministically polynomial time verifiable solution for the proof of C's decision problem (in other words, we can "quickly" verify the solution to the optimization version of the problem), it can be expressed as a satisfiability problem which asks for: what input satisfies the verification conditions - this is a satisfiability problem, what remains is to "booleanize" it, as one would when making a logic circuit to verify the solution.

In this sense, $\rm C{\small IRCUIT}\text{-}S{\small AT}$ is a/the "language" of non-determinism (but ofc this is arbitrary, other $\rm NPC$ problems might just as easily be able to express the problem).

$\endgroup$
4
$\begingroup$

If $S$ is $NP$-complete, then any other problem in $NP$ can be reduced to $S$, in polynomial time. So any $NP$ problem $C$ can be reduced to $S$ in polynomial time, and then solved (as $S$) in polynomial time. Thus, $C$ has been solved in polynomial time itself.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .