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.
1
$\begingroup$
$\endgroup$
3
$\begingroup$
$\endgroup$
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.
-
$\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
