# Why any problem can be reduced to SAT is NP-Complete?

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 Answer

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.

• Thank you so much, I also suspected that the book is incorrect. – Bit_hcAlgorithm Jan 1 at 14:31
• 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. – Auberon Jan 1 at 14:43
• @Auberon Indeed. The "incorrect" statement is the one in the question title. – dkaeae Jan 1 at 18:46