> 7.1 million core-hours of processing time on a machine with 640 Intel Xeon hex-core processors. They started in January 2011 and finished in December.
Though the paper at https://arxiv.org/abs/1201.0749 says Sudoku solving is "only" NP-complete, so it's not really an example of "harder than NP-Complete".
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.
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."
"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.
> 7.1 million core-hours of processing time on a machine with 640 Intel Xeon hex-core processors. They started in January 2011 and finished in December.
Though the paper at https://arxiv.org/abs/1201.0749 says Sudoku solving is "only" NP-complete, so it's not really an example of "harder than NP-Complete".