Jeff wrote:Using language that everyone can understand, could you explain "exponential number of operations when extrapolated to the NxN case" and "polynomial number of operations"? How can these numbers be calculated? Can you give a few simple examples? Can T&E be defined within the 9x9 case, which is what 99% of players are interested in this forum?
To determine the complexity of a technique, simply count the number of operations required to carry it out. If that number is proportional to a simple power of N, the complexity is polynomial; if it's some number to the Nth power, that makes the technique exponential.
Full backtracking is the best example of an exponential technique in sudoku. Limited backtracking (e.g. Nishio) can be polynomial, but doesn't always succeed. Looking for pairs is polynomial (proportional to N^2).
The presence of backtracking is perhaps the tell-tale sign of any trial and error (i.e. exponential) technique.
Jeff wrote:Using language that everyone can understand, could you explain "a set of polynomial-time techniques", "single-digit sudoku decision problem" and "NP-complete for the general NxN case"?
You might wish to check out the following thread:
http://www.setbb.com/phpbb/viewtopic.php?t=393&start=0&mforum=sudoku
Mark
