4 ms·

Thanks for the reference, and I’d misremembered the amount of CPU required. However, I will say that while solving sudoku is np-complete, this “finding minimal

Thanks for the reference, and I’d misremembered the amount of CPU required. However, I will say that while solving sudoku is np-complete, this “finding minimal” problem is harder than np-complete — it is common to have situations where solving a problem is np-complete, but then asking what is the biggest/hardest/smallest/etc problem is harder than np-complete.

eesmith 3y ago
I'm not criticizing. I think less than an order of magnitude from an off-the-head memory is just fine. And after 10 years, computers have gotten more powerful. ;) I misread the paper. I think is saying that finding the minimal size is NP-complete. Here's the abstract: "The hitting set problem is computationally hard; it is one of Karp’s 21 classic NP-complete problems. A standard backtracking algorithm for finding hitting sets would not be fast enough to search for a 16-clue sudoku puzzle exhaustively, even at today’s supercomputer speeds." For context, https://arxiv.org/pdf/1601.02939.pdf https://arxiv.org/pdf/1601.02939.pdf says: "It has been known since Karp’s seminal 1972 paper [42] that the problem of determining whether a given set family has a hitting set of size no greater than some k is NP-complete.