1
$\begingroup$

A problem $L$ is NP-complete when:-

  1. $L\in \text{NP}$
  2. For every problem $L' \in \text{NP}$, $L'$ is polynomial time reducible to $L$

When at least property 2 is satisfied for a problem $L$ (but not necessarily property 1), then $L \in \text{NP-Hard}$.

When a problem $L\in \text{NP-Complete}$ is shown to have a polynomial-time solution, we say $\text{P}=\text{NP}$ due to Cook-Levin Theorom.

Wikipedia states:

An important consequence of the theorem is that if there exists a deterministic polynomial time algorithm for solving Boolean satisfiability, then there exists a deterministic polynomial time algorithm for solving all problems in NP. Crucially, the same follows for any NP complete problem.

This can be attributed to transitivity property of polynomial-time reductions.

If we are able to show that a problem $L''$ already known to be in NP-complete to be polynomial-time reducible to the problem $L$, then $L$ satisfies property 2 by transitivity.

Well as the property 2 is satisfied by the NP-Hard problems too.

My assumptions -

  1. A known NP-Hard problem is polynomial-time reducible to a unknown problem $L$. Then $L$ should satisfy property 2 too. So, $L$ is NP-Hard. If $L\in \text{NP}$ also true, then $L\in \text{NP-complete}$.
  2. If $L \in \text{NP-Hard}$ but not shown to be NP yet and we have a deterministic polynomial-time algorithm for $L$ then $\text{P}=\text{NP}$.

Now, my questions-

  1. Are my assumptions above true? - Wikipedia says it is true. Please confirm and provide other good references to check my assumptions.
  2. If above is true, why are the NP-Complete class considered so important when the answer to P=NP rests on existence of a deterministic polynomial-time algorithm to any NP-Hard problem (be it NP-Complete or not)?
$\endgroup$
2
  • $\begingroup$ @Kyle Thanks! I agree that the question is a duplicate. But I want the references part answered by someone - someone might give the reference to a detailed book that has my assumptions as lemma. I'll be keeping the question open for a while. $\endgroup$ Jun 21 '15 at 23:01
  • $\begingroup$ That's not how it works -- we don't keep duplicate questions open. If you have a specific question that isn't answered by that other question, please edit your question to ask only about the specific part that isn't covered by any existing question. However, note that we generally don't do "please check my answer" -- the only answer to those questions are "Yes" or "No", and that's unlikely to help future visitors. Similarly, I recommend rather than asking for references you ask for information or explanation. $\endgroup$
    – D.W.
    Jun 21 '15 at 23:36