0
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2016 at 18:44
  • $\begingroup$ I thought that SAT was not (NP)hard. $\endgroup$
    – Dietrich Burde
    Feb 15, 2016 at 18:45

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you .. Great and clear explanation :) $\endgroup$
    – Michael
    Feb 15, 2016 at 18:56
  • $\begingroup$ Thank you. I strive to be clear and thorough in my exposition :) $\endgroup$
    – MonadBoy
    Feb 15, 2016 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, 2016 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$
    – MonadBoy
    Feb 15, 2016 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, 2016 at 21:20

You must log in to answer this question.

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