mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Viliam Furik

Reply
 
Thread Tools
Old 2021-07-21, 09:29   #12
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24×613 Posts
Default

Replying to the topic title, if you can prove P=NP, then getting the million bucks is the smallest and least important thing that will happen to you in the next 20 years.

Replying to the most recent discussion, does that mean you have an algorithm that solves generalized sudoku without guessing (i.e. without backtrack)? If so, I would really die to know it, haha. Or sell my soul to the devil, if not sold already, but I believe he won't want it, it would not be a good business for him. Mind that I consider myself a very strong sudoku solver, say top 0.01% world solvers. But I will wait for the official paper to read about that

Good luck.

Anyhow, as a way to go forward for your team, you could try to transform your algorithm to solve hamiltonian cycle or 3-sat, and I believe there are algorithms on the web to transform generalized sudoku into one of these or viceversa. Telling people about sudoku, they are reticent. Tell them about graphs and boolean circuits, you got them by the ears.

Funny fact: I used to strongly believe that P=NP too, and many times I got into arguments with my professors because of it. I still believe it, but not so strong anymore. Now it is more like a "hope" . Some of my professors, those who had an opinion (mostly didn't dare to risk it, and preferred to stay at the fact side), believed the contrary, because "otherwise, anybody will be a Mozart". If we would be able to find solutions to problems with about the same speed we can verify that a given solution is right, then writing a symphony, or more thematic, proving a lot of math theory and physics phenomenon, would not take much longer than listening and appreciating the beauty of that same symphony or proof. I was thinking for a while that only our stupidity (i.e. we do not have yet the right algorithms, our current stage of evolution is not high enough, whatever) impede anybody to be a Mozart. I still believe that, by the way, and this has not much to do with P or NP. My way to "prove P=NP" was for a while (read: few years spent in uni and after) related to perfect graphs. These perfect graphs have nice colorability properties, i.e. most coloration problems are polynomial. And every NP-complete problem can be reduced to a graph problem, and as every graph problem can be reduced to a coloration problem in a graph, and as all graphs with few exceptions are perfect graphs (at the time this was called "Berge conjecture", it was later proved and became the Strong Perfect Graph's Theorem), you see the consequence. It follows that all NP-complete problems are polynomial with few exceptions, but for the exceptions (non-Berge graphs) the coloring is trivial (i.e. hamiltonian cycle in an odd cycle graph is just the cycle itself, and in its complementary there is a simple linear algorithm to find it). The most of these "inclusions" are already proved, and I still believe that the way to go for showing P=NP is through perfect graphs and coloration. But few things were shaking my belief since that time, one of these few things was reading the SPG proof when it came out. Another was reading (some years ago) about the fact that generalized sudoku is NP-complete . Because I can't imagine how somebody will solve a well made sudoku grid without backtracking. If you don't believe me, try this grid, without guessing. Courtesy of Mark and Simon, from Cracking the Cryptic youtube channel (google them, it is fun!). This grid is trivial to solve by guessing, but almost impossible to solve by logic, as they proved in two videos. Then think about a 169x169 grid (with 13x13 biscuits) and tell my how would you solve THAT one in O(n^6) You can have few hundreds of chains, every one of them with a hundred links, and you will have to make few hundred guesses, fill each chain, and if the guess was wrong and you got a contradiction, you will need to backtrack and refill with the correct chain. I don't see other way. But again, I may be too stupid to be a Mozart, haha
Click image for larger version

Name:	mark_and_simon_01.JPG
Views:	119
Size:	27.4 KB
ID:	25315

Last fiddled with by LaurV on 2021-07-21 at 10:33
LaurV is offline   Reply With Quote
Old 2021-07-21, 14:18   #13
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

13028 Posts
Default

Quote:
Originally Posted by LaurV View Post
Anyhow, as a way to go forward for your team, you could try to transform your algorithm to solve hamiltonian cycle or 3-sat, and I believe there are algorithms on the web to transform generalized sudoku into one of these or viceversa. Telling people about sudoku, they are reticent. Tell them about graphs and boolean circuits, you got them by the ears.
I tried that. It didn't pan out so far. There is almost a trivial relation to the Latin squares, but the rest is not as easy to do.

Quote:
Originally Posted by LaurV View Post
If you don't believe me, try this grid, without guessing. Courtesy of Mark and Simon, from Cracking the Cryptic youtube channel (google them, it is fun!). This grid is trivial to solve by guessing, but almost impossible to solve by logic, as they proved in two videos. Then think about a 169x169 grid (with 13x13 biscuits) and tell my how would you solve THAT one in O(n^6) You can have few hundreds of chains, every one of them with a hundred links, and you will have to make few hundred guesses, fill each chain, and if the guess was wrong and you got a contradiction, you will need to backtrack and refill with the correct chain. I don't see other way. But again, I may be too stupid to be a Mozart, haha
I know them, great channel indeed!

I'll send you more details on inner working of the algorithm in PM (as well as the results of the experiment), but this I will say "publicly":

I should be able to get a solution in O(n^12) - unless I found a counterexample to the algorithm. In O(n^6), I should be able to tell you whether it's uniquely solvable, non-uniquely solvable, or non-solvable. The part about being able to distinguish between unique solutions and non-unique ones is not well-studied yet. It's only simple observation. But the same observation tells me, that if it is uniquely solvable, I should be able to get a solution in O(n^6).

EDIT:
After running the experiment, I found that at least for the present version of the algorithm, the striken is not true.

Last fiddled with by Viliam Furik on 2021-07-21 at 14:32
Viliam Furik is offline   Reply With Quote
Old 2021-07-21, 20:38   #14
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

25×3×5 Posts
Default

Quote:
Originally Posted by LaurV View Post

Thanks, my 77-year old, sudoku-addicted mother will love it
Till is offline   Reply With Quote
Old 2021-07-21, 21:12   #15
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2C216 Posts
Default

Quote:
Originally Posted by Till View Post
Thanks, my 77-year old, sudoku-addicted mother will love it
You can google some n=4 grids for her, that's an even bigger challenge. I attached one such grid.
Attached Thumbnails
Click image for larger version

Name:	16x16-350.gif
Views:	66
Size:	22.0 KB
ID:	25317  
Viliam Furik is offline   Reply With Quote
Old 2021-07-21, 22:16   #16
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Gracie on alert.

34×5 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
That's possible, but I doubt the script runs in polynomial time.

Yes, they did. But none of them produced a general polynomial-time algorithm, as Wikipedia still states the problem is NP-complete.
Definitely no poly time script on a classical (binary) system that I'm aware of but there are some good solvers out there.
jwaltos is offline   Reply With Quote
Old 2021-07-21, 22:59   #17
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2·353 Posts
Default

Quote:
Originally Posted by jwaltos View Post
Definitely no poly time script on a classical (binary) system that I'm aware of but there are some good solvers out there.
That's true.
Viliam Furik is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What are the most exciting things that can happen in order of likelihood? EugenioBruno Information & Answers 21 2020-03-28 21:12
What will happen? RichardB Information & Answers 16 2010-09-03 21:25
Which will happen first? Uncwilly Lounge 11 2005-02-18 14:41

All times are UTC. The time now is 23:33.


Sat Dec 4 23:33:20 UTC 2021 up 134 days, 18:02, 1 user, load averages: 0.81, 1.08, 1.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.