4 ms·

Finding and understanding computational algorithms is part of my daily work. I know what time complexity means. By saying NP-hard, I mean an NxN sudoku cannot b

Finding and understanding computational algorithms is part of my daily work. I know what time complexity means. By saying NP-hard, I mean an NxN sudoku cannot be solved in time polynomial to N. Most sophisticated sudoku solving algorithms, including mine, do not assume the grid has a solution or one solution. They test and give all possible solutions. I am really trying to solve an NPC problem. That said, your comment still tells me something I do not know - you seems to say that given a sudoku that is known to have one solution, there may be polynomial algorithms. This reminds me of someone who left a comment in my blog, saying that if the solution is unique, at each step there are at most two choices with the exact cover matrix. He couldn't prove that, but his program run happily on tens of thousands of Sudokus without problems. This does not necessarily solve sudoku in polynomial time, but may make solvers faster for unique sudokus.

yaakov34 14y ago
Yeah, I have no problem with that if it's viewed as an NxN problem. I do have a slight tic about this since I've heard "NP-hard" misused so often, including by one guy at a former workplace whose program needed to test all 6 permutations of something-or-other to discover the optimum one, and that was "NP-complete", you see. About the complexity of Sudoku which is known to have a unique solution: I didn't say there is a polynomial algorithm for it. It's equivalent to the Unambiguous SAT problem, and Valiant and Vazirani proved that it's in some sense almost as hard as the SAT problem itself. You can't call it NP-complete (because that's not known), but if there is a polynomial algorithm for it, then there is a probabilistic polynomial algorithm for every problem in NP; and since you can run a probabilistic algorithm as many times as you want and get independent results, you'd be able to solve every decision problem in NP with immense certainty (although less than 1). About efficient algorithms for Sudoku, I think that the crux here is average case complexity (defined in some way over the sort of samples you are using). It's not clear to me that average case complexity for Sudoku is high, at least for the kind of puzzles we know how to generate. Certainly solvers based on backtracking seem to handle them very well. It's very hard to prove results about that, though. In any case, if someone has a polynomial time algorithm for Unambiguous SAT, or something equivalent to it, that would pretty amazing (but I doubt it - the average time might be very good, though).
- attractivechaos 14y ago
  Thanks for these info. I appreciate.

yaakov34 14y ago

Yeah, I have no problem with that if it's viewed as an NxN problem. I do have a slight tic about this since I've heard "NP-hard" misused so often, including by one guy at a former workplace whose program needed to test all 6 permutations of something-or-other to discover the optimum one, and that was "NP-complete", you see. About the complexity of Sudoku which is known to have a unique solution: I didn't say there is a polynomial algorithm for it. It's equivalent to the Unambiguous SAT problem, and Valiant and Vazirani proved that it's in some sense almost as hard as the SAT problem itself. You can't call it NP-complete (because that's not known), but if there is a polynomial algorithm for it, then there is a probabilistic polynomial algorithm for every problem in NP; and since you can run a probabilistic algorithm as many times as you want and get independent results, you'd be able to solve every decision problem in NP with immense certainty (although less than 1). About efficient algorithms for Sudoku, I think that the crux here is average case complexity (defined in some way over the sort of samples you are using). It's not clear to me that average case complexity for Sudoku is high, at least for the kind of puzzles we know how to generate. Certainly solvers based on backtracking seem to handle them very well. It's very hard to prove results about that, though. In any case, if someone has a polynomial time algorithm for Unambiguous SAT, or something equivalent to it, that would pretty amazing (but I doubt it - the average time might be very good, though).

attractivechaos 14y ago
Thanks for these info. I appreciate.