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.
can humans accurately (not heuristically) solve sudoku in polynomial time though? also, polynomial in relation to what - grid size, number of empty squares?
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
>>14 The likely situation here is: 1.a NP solver with backtracking/guessing is very optimized and is very common solution: it however doesn't scale to large problems. 2. a theoretical deterministic solver is not optimized, but if optimized would scale much better than any NP-solver(which is essentially difference between fast brute-force and constraint solving). It scales great with size of problem, however due factor of scaling these advantages become apparent only at very large boards. Optimization makes the algo run faster on smaller boards. i.e. it becomes optimal at all scales.
Name:
Anonymous2016-09-21 10:14
>>16 the solver might be deterministic but is it polynomial deterministic?
Name:
Anonymous2016-09-21 10:43
>>17 Do you understand what NP mean? The solver described is deterministic. i.e. its not NP anymore. In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-C or NPC. The abbreviation NP refers to "nondeterministic polynomial time".
Name:
Anonymous2016-09-21 10:51
>>18 the existence of a deterministic solver does not make it P because to be P it must be deterministic and polynomial (or faster). a deterministic solver can work in exponential (or slower) time
Name:
Anonymous2016-09-21 10:55
from the pdf its explicitly stated its polynomial time solver:
The continuous-time dynamical system [13] (2-3) as a deterministic algorithm does have these features: 1) the search happens on an energy landscape V = P m a m K 2 m that incorporates simultaneously all the constraints (problem structure) 2) it solves easy problems efficiently (polynomial time, both analog and discrete) and 3) it guarantees to find solutions to hard problems even for solvable cases where many other algorithms fail. Al- though it is not a polynomial cost algorithm, it seems to find solutions in continuous-time t that scales poly- nomially with N [13]. These features and the fact that the algorithm is formulated as a deterministic dynami- cal system with continuous variables, allows us to apply the theory of nonlinear dynamical systems on CTDS (2- 3) to characterize the hardness of Boolean satisfiability problems. In particular, via the measurable escape rate κ, or its negative log-value η, we can provide a single- scalar measure of hardness, well defined for any finite instance. We have illustrated this here on Sudoku puz- zles, but the analysis can be repeated on any other en- semble from NP
Name:
Anonymous2016-09-21 15:36
A FrozenAnus-like entity is taking over this thread. Please hide in your designated bunkers.
I've spent all day solving sudoku puzzles at highest level. Some insights: 1. its really slow to solve, especially when its unclear which path you should take(from two). 2.I haven't used any advanced technique, except block-row elimination(if line in block row/column is filled with only number X, the rest of row/column cannot contain the number. 3.The most effecting solving technique by speed is setting constraints on which numbers cannot be in block/row/col and if there is only one number that can be placed - its the correct number.
Name:
Anonymous2016-09-22 12:02
>>25 Because autisms can be funny. In a laughing at, not laughing with sense, of course.
>>35 The compiling process can easily be modeled as a mathematical function that takes in a human readable program and outputs the corresponding computer binary program.
Name:
Anonymous2016-09-23 1:17
>>1 that's cause every odd number + arbitrary odd number = even number lel