Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

P == NP proof

Name: Anonymous 2016-09-21 4:34

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.

[1]http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html

Name: Anonymous 2016-09-21 9:46

>>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.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List