Re:Misconceptions about NP-Completeness (Score 1)

Well - there certainly are efficient solvers for many instances for NP-complete problems. For example, state of the art SAT solvers (mini-SAT) can solve huge instances of many satisfiability problems, and with respect to Sudoku, state of the art CSP solvers (Minion) can solve many instances of sudoku. The problem is that some instances of the problems are very ill-conditioned, so in on these instances, even state of the art SAT, CSP, and QBF solvers will show exponential time complexity. CSP and SAT solvers use a mixture of search and inference to prune the search space of these probems dramatically, but some instances just don't work well with this technique. So the question becomes more than just can it solve a 9X9 sudoko, it's how it solves this problem. If it solves the problem using "quantum computing", I don't think it should matter what instance of 9X9 sudoku, it should solve them all relatively quickly. If it's not using quantum computing, the question becomes would any instances cause exponential behavior.