mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Viliam Furik (https://www.mersenneforum.org/forumdisplay.php?f=174)
-   -   What might really happen if P=NP? (https://www.mersenneforum.org/showthread.php?t=26855)

Viliam Furik 2021-05-30 22:45

What might really happen if P=NP?
 
Hi, I have been recently interested in this topic. Together with my schoolmate, we may have found an algorithm to solve an NP-complete problem, but nothing is sure for now, so I won't go into much detail about it, except that it should be able to determine the solvability of the said problem in O(n[SUP]6[/SUP]) and find a solution in O(n[SUP]12[/SUP]) - take the O-times with a grain of salt, I may have made a mistake when determining them.

So my question is: How much of use (and in which areas of science and life) would this algorithm have if it turned out to be correct?

I heard and read about GPS navigation ride routing, for example. How big and complicated of a ride would need to be planned in order for it to benefit from the algorithm?

R. Gerbicz 2021-05-30 23:00

[QUOTE=Viliam Furik;579517]Together with my schoolmate, we may have found an algorithm to solve an NP-complete problem
...
So my question is: How much of use (and in which areas of science and life) would this algorithm have if it turned out to be correct?[/QUOTE]

That would mean 1M bucks for you: [url]https://en.wikipedia.org/wiki/Millennium_Prize_Problems[/url]. Maybe that is before tax, but I'm not really a tax expert here.
And instead of you I'd stick to these problems. Who knows you could destroy the remaining problems also.

Viliam Furik 2021-05-30 23:09

Yes, I know there is a 1M $ prize for its head... But I also know that it can be awarded after two years from publishing. So I wanted to ask about its real use as an algorithm. There are many claims that if P=NP every difficult task will get easy and life will become topical, basically. I want to find out, how close it is to the truth, or how far from it.

mathwiz 2021-05-30 23:18

Your question presupposes that the proof will be constructive, i.e. that it shows how to take a problem in NP and solve in polynomial time.

It could be that someone proves P=NP but the proof does not provide sufficient information for transforming a problem in NP to an equivalent in P.

chalsall 2021-05-30 23:26

[QUOTE=mathwiz;579521]It could be that someone proves P=NP but the proof does not provide sufficient information for transforming a problem in NP to an equivalent in P.[/QUOTE]

Add to this those who think Quantum Computing will end the world...

"Umm... OK... Let's start with the basics... Just how many qubits do you need to represent the problem?

The silence generally starts about there and then continues for all the following questions...

retina 2021-05-30 23:40

Proving P=NP in no way guarantees you can then find P algorithms for all NP problems. Maybe you could, maybe you couldn't. It depends upon the nature of the proof.

All it would say is that an algorithm exists. It might not say how to find it.

It is even possible that someone could prove P=NP, but still no one can find any algorithm to solve any NP problem in P time.

You appear to have the opposite. You have an NP problem and a P solution. And if true then great ... for that problem. But would it lead to solving all other NP problems? Only you can tell us by explaining what you have.

Viliam Furik 2021-05-31 08:30

[QUOTE=retina;579524]You appear to have the opposite. You have an NP problem and a P solution. And if true then great ... for that problem. But would it lead to solving all other NP problems? Only you can tell us by explaining what you have.[/QUOTE]
It's an NP-complete problem, so if the internet's wisdom is right, then any NP problem should be "transformable" to this NP-complete problem, i.e. for any problem in NP, there should exist its counterpart in this problem.

I prefer to keep my algorithm for myself (mainly because I don't want to act like the few forum users which come here to shove their "discoveries" down our throats) until I and my schoolmate meet with a few people from Comenius University in Bratislava, where I am also going to study.

chalsall 2021-05-31 19:24

[QUOTE=Viliam Furik;579538]I prefer to keep my algorithm for myself (mainly because I don't want to act like the few forum users which come here to shove their "discoveries" down our throats) until I and my schoolmate meet with a few people from Comenius University in Bratislava, where I am also going to study.[/QUOTE]

That's fine. You've most likely made a mistake.

But if you haven't, it will be a *big* deal.

Edit: A bit of learned levity... Two economists are walking down the street. One asks the other "Is that a 20-pound note just laying there in the street?" The other economist answers immediately without even looking: "No. Of course not! Or else someone else would have already picked it up.

Viliam Furik 2021-07-20 22:10

I have a few updates on this topic.

1. The proof of correctness for the algorithm is not as correct as I thought... But it's incorrect in a way that the proof for one key aspect of the algorithm is missing, which still allows the possibility of it being true, but it's hard to say for sure without good proof.

2. Meanwhile, a friend of our friend helped us find a counterexample, in which the algorithm failed. It was basically a type of infinitely many counterexamples. But we have managed to quickly patch it up by adding a feature (basically error-check), which we actually considered in the creation process, but thought it can not be done in polynomial time, so we ignored it. Turns out, it is doable in polynomial time... So far, we haven't come up with another counterexample.

We are trying to find proof of correctness or another counterexample, but so far no luck with either. So if there is someone with enough free time and willing to help, we will be happy to have another helping hand (brain, actually).

The problem the algorithm is solving is Generalised Sudoku, i.e. Sudoku where the grid is made of n by n squares of n by n cells. The classic newspaper Sudoku is n=3.

We have a working (the updated version works for all tested grids so far) implementation of the algorithm in Python, which is not a fast language, but it is the only one I know well enough and it's quite easy to make such implementations in it.

If you are willing to help in any way, please, send me a PM.

jwaltos 2021-07-20 23:32

I recall reading somewhere that Stephen Wolfram wrote a 3 line Perl script that would solve Soduku..similar to a minesweeper script.
Along those lines, Dijkstra's algorithm - Wikipedia, Knuth, Kaye and a few others should have crossed your path regarding this investigation.

Viliam Furik 2021-07-21 00:01

[QUOTE=jwaltos;583622]I recall reading somewhere that Stephen Wolfram wrote a 3 line Perl script that would solve Soduku..similar to a minesweeper script.
Along those lines, Dijkstra's algorithm - Wikipedia, Knuth, Kaye and a few others should have crossed your path regarding this investigation.[/QUOTE]

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.

LaurV 2021-07-21 09:29

1 Attachment(s)
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 :razz:

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" :razz:. 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 [URL="https://en.wikipedia.org/wiki/Strong_perfect_graph_theorem"]Strong Perfect Graph's Theorem[/URL]), 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 :lol: when it came out. Another was reading (some years ago) about the fact that generalized sudoku is NP-complete :razz:. 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) :shock: 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 :lol:
[ATTACH]25315[/ATTACH]

Viliam Furik 2021-07-21 14:18

[QUOTE=LaurV;583641]
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.
[/QUOTE]
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=LaurV;583641]
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) :shock: 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 :lol:[/QUOTE]
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. [STRIKE]But the same observation tells me, that if it is uniquely solvable, I should be able to get a solution in O(n^6).[/STRIKE]

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

Till 2021-07-21 20:38

[QUOTE=LaurV;583641]
[ATTACH]25315[/ATTACH][/QUOTE]


Thanks, my 77-year old, sudoku-addicted mother will love it :cool:

Viliam Furik 2021-07-21 21:12

1 Attachment(s)
[QUOTE=Till;583694]Thanks, my 77-year old, sudoku-addicted mother will love it :cool:[/QUOTE]

You can google some n=4 grids for her, that's an even bigger challenge. I attached one such grid.

jwaltos 2021-07-21 22:16

[QUOTE=Viliam Furik;583623]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.[/QUOTE]

Definitely no poly time script on a classical (binary) system that I'm aware of but there are some good solvers out there.

Viliam Furik 2021-07-21 22:59

[QUOTE=jwaltos;583704]Definitely no poly time script on a classical (binary) system that I'm aware of but there are some good solvers out there.[/QUOTE]

That's true.


All times are UTC. The time now is 06:50.

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