4 ms·
You'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 bin
by jcranmer 1y ago
You'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!