Sudoku solving is NP complete[1] Human brains can solve sudoku in polynomial time There exists one example of polynomial time solving of a NP complete problem => P == NP.
Probably unoptimized algorithms. Can you link me a C source for the fastest solver and i'll check if its optimal?
Name:
Anonymous2016-09-21 8:58
>>8 wtf are you talking about? my point is: solvers can solve sudoku quickly because the problem size is small (standard sudoku: 9x9 grid, 9 symbols, 17-20 non-empty fields). the question of NP-completeness and P-NP problem is not related to that, it's related to how this execution time (or rather number of needed steps) changes when those parameters change. how long would it take to calculate a generalized sudoku on, for example, 20x20 grid, 20 symbols and 10 non-empty fields?
Name:
Anonymous2016-09-21 9:06
Human brains are finitely-bound non-deterministic Turing machines due to their highly parallel nature, so of course they can appear to solve NP complete problems in P time by brute-force, so long as the workload is within a certain bound.
It's no different than throwing a supercomputer with 40,000 cores at an NP-complete problem and then claiming that because the supercomputer solved it in 1/40,000th and that it seems to match up with what you would expect for an algorithm that runs in polynomial time due to the finite bound of the problem, that therefore a single core in the supercomputer is the same as the entire supercomputer and thus P == NP.
But if you scale up the work without scaling up the number of cores, you'll find the asymptotes diverge and you get something that runs in NP time again.
Increase the size of a Sudoku board to 1296x1296 and you'll find that the human brain can't keep up and it's back to solving it in NP time.
Name:
Anonymous2016-09-21 9:09
>>9 I'm not interested in theoretical aspects, just optimization problem. If given a fastest solver that solves X at N cpu cycles, N will be reduced substantially by optimization. I'll benchmark it on a specific puzzle and post improvements here.
Name:
Anonymous2016-09-21 9:13
>>11 but that has nothing to do with the subject of this thread which is about the NP-completeness of sudoku and possibilitty of solving it in P