Kindly, I have two questions:

(1) Are NP-hard, NP-problem, and NP-Complete are just synonyms of each other?

(2) I understand that SAT is NP problem that cannot be solved in polynomial time complexity. I just would like to see an example that shows how SAT requires exponential time instead.

Thank you.

  • $\begingroup$ You are wrong about the meaning of $NP$ - it isn't known whether $SAT$ can be solved in polynomial time by a deterministic turing machine. But if it can, then every problem in $NP$ can. $\endgroup$ – Stefan Mesken Feb 15 '16 at 18:44
  • $\begingroup$ I thought that SAT was not (NP)hard. $\endgroup$ – Dietrich Burde Feb 15 '16 at 18:45

You seem to have the concepts a little confused. Let us sort things out:

(1) No, the words NP-hard, NP problem and NP-Complete are not synonyms of each other. NP is the class of problems that can be solved by a nondeterministic polynomial-time Turing machine.

A problem is an NP problem if it lies in NP (so, if it is solvable in poly-time by a nondeterministic Turing machine).

A problem is NP-hard if every instance of all other problems in NP can be translated to instances of it in deterministic polynomial time. Note that an NP-hard problem doesn't have to lie in NP by this definition.

A problem is NP-complete if it is both an NP problem and NP-hard.

(2) There are currently no examples found of exponential-time SAT instances, nor any proof that such examples don't exist. The whole point of the P=NP question is whether or not all problems in NP (SAT included) can be solved in deterministic polynomial time. If there were an exponential-time SAT instance, this would immediately have solved the problem in the negative. As for whether or not such a thing exists, we simply don't know as of yet.

  • $\begingroup$ Thank you .. Great and clear explanation :) $\endgroup$ – Michael Feb 15 '16 at 18:56
  • $\begingroup$ Thank you. I strive to be clear and thorough in my exposition :) $\endgroup$ – A.Sh Feb 15 '16 at 18:57
  • $\begingroup$ Can I ask another: I want to see an example to show SAT is NP problem. Just to understand how it becomes NP. THANK YOU $\endgroup$ – Michael Feb 15 '16 at 18:58
  • $\begingroup$ Perhaps this could have been its own question, but ok. Nondeterminism is, intuitively, "programmed luck" in the sense that whenever there is a choice to be made in computation, we always make the correct one. (Another way to see this is by introducing "witnesses" that encode the choices, but I don't have enough space to explain) To see that SAT is in NP, take a SAT instance. We can "nondeterministically choose" (make lucky guesses) if each variable in the formula is true or false. Guessing and evaluating takes poly-time, and by the end we know if the instance was satisfiable. So SAT is in NP. $\endgroup$ – A.Sh Feb 15 '16 at 19:12
  • $\begingroup$ (Guessing and evaluating takes poly-time, and by the end we know if the instance was satisfiable) which means 2^n otherwise!!! this sums up what I want. THANK YOU $\endgroup$ – Michael Feb 15 '16 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.