1
$\begingroup$

I have a book statement says the title, I don't understand it. From my current understanding if a problem A can be reduced to a problem B then it only means B is at least as difficult as A.

$\endgroup$
3
$\begingroup$

Indeed that is incorrect. All problems in $\mathbf{P}$ are reducible to SAT. In fact, even trivial problems (e.g., finite languages) are reducible to SAT.

What is probably meant is that, if a problem in $\mathbf{NP}$ is such that SAT is reducible to it, then it is $\mathbf{NP}$-complete.

$\endgroup$
  • $\begingroup$ Thank you so much, I also suspected that the book is incorrect. $\endgroup$ – Bit_hcAlgorithm Jan 1 at 14:31
  • $\begingroup$ I might be missing something but " if a problem A can be reduced to a problem B then it only means B is at least as difficult as A" is not an incorrect statement. $\endgroup$ – Auberon Jan 1 at 14:43
  • 2
    $\begingroup$ @Auberon Indeed. The "incorrect" statement is the one in the question title. $\endgroup$ – dkaeae Jan 1 at 18:46

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.