4 ms·
> Basically, they show that you can use SAT to solve Sudoku, and then claim that this makes Sudoku NP-complete. (All it shows is that Sudoku is in NP.) Wait, d
by dataflow 1y ago
> Basically, they show that you can use SAT to solve Sudoku, and then claim that this makes Sudoku NP-complete. (All it shows is that Sudoku is in NP.)
Wait, did you mess up the direction here too, or am I confused? If you reduce problem A to B, then it means B is at least as hard as A, because solving it would solve A. Which certainly means in this case that Sudoku is NP-hard. And it doesn't (without introducing additional facts) imply Sudoku is in NP either. I don't see anything wrong here, do you?
- andrewla 1y agoNo, the GP is correct. If you use SAT to solve Sudoku, you have reduced Sudoku to SAT, not the other way around. That is, you've shown that an oracle that solves any SAT problem in constant time can solve any Sudoku in polynomial time. The more difficult side is to show that for any SAT instance, you can reduce it to a Sudoku. Really proving that you can use SAT to solve Sudoku is not a great or interesting result; since Sudoku is a decision problem it is very clear that it is in NP. Or see that verifying that a Sudoku solution is correct is achievable in polynomial time.
- mzl 1y ago> > they show that you can use SAT to solve Sudoku > Wait, did you mess up the direction here too, or am I confused? If you reduce problem A to B, then it means B is at least as hard as A, because solving it would solve A. Using SAT to solve Sudoku is a reduction of Sudoku to SAT. The order of the problems names switches depending on how you write it.
- dataflow 1y agoThanks, yeah, that's what I messed up. I was so focused on the reduction direction that I misparsed the statement.
- jcranmer 1y agoYou've messed up the direction here. Reducing unknown-complexity to NP-complete means you can bound the complexity by above, but not by below. I can reduce binary integer addition to SAT, which means that binary integer addition is no harder than SAT... but we also know by other algorithms that it is in fact easier than SAT. To bound by below, you have to reduce NP-complete (or NP-hard suffices) to unknown-complexity.
- dataflow 1y agoOh gosh. I think I was so focused on the reduction direction that I think I misread the premise of the comment -- it seems somehow my brain parsed "use SAT to solve Sudoku" as "solve SAT using Sudoku". That's why I was saying that reducing SAT to Sudoku would imply Sudoku is at least as hard as SAT. It indeed would if they had actually done that, but they did the opposite. Not sure how my wires got crossed when reading, but thanks!
- almostgotcaught 1y ago> I don't see anything wrong here, do you? Lololol
- eru 1y agoYeah, this is a confusing topic and easy to get wrong!