mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-05-30, 22:45   #1
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

10101010002 Posts
Default 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(n6) and find a solution in O(n12) - 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?
Viliam Furik is online now   Reply With Quote
Old 2021-05-30, 23:00   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×32×83 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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?
That would mean 1M bucks for you: https://en.wikipedia.org/wiki/Millennium_Prize_Problems. 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.
R. Gerbicz is offline   Reply With Quote
Old 2021-05-30, 23:09   #3
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

23·5·17 Posts
Default

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.
Viliam Furik is online now   Reply With Quote
Old 2021-05-30, 23:18   #4
mathwiz
 
Mar 2019

23·52 Posts
Default

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.
mathwiz is online now   Reply With Quote
Old 2021-05-30, 23:26   #5
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2·13·383 Posts
Default

Quote:
Originally Posted by mathwiz View Post
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.
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...
chalsall is online now   Reply With Quote
Old 2021-05-30, 23:40   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

188A16 Posts
Default

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.
retina is offline   Reply With Quote
Old 2021-05-31, 08:30   #7
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

23·5·17 Posts
Default

Quote:
Originally Posted by retina View Post
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.
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.
Viliam Furik is online now   Reply With Quote
Old 2021-05-31, 19:24   #8
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2·13·383 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
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.
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.

Last fiddled with by chalsall on 2021-05-31 at 19:29
chalsall is online now   Reply With Quote
Old 2021-07-20, 22:10   #9
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

23·5·17 Posts
Default

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.
Viliam Furik is online now   Reply With Quote
Old 2021-07-20, 23:32   #10
jwaltos
 
jwaltos's Avatar
 
Apr 2012
Gracie on alert.

19016 Posts
Default

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.

Last fiddled with by jwaltos on 2021-07-20 at 23:32
jwaltos is offline   Reply With Quote
Old 2021-07-21, 00:01   #11
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

23×5×17 Posts
Default

Quote:
Originally Posted by jwaltos View Post
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.
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.
Viliam Furik is online now   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 01:42.


Fri Oct 22 01:42:59 UTC 2021 up 90 days, 20:11, 2 users, load averages: 2.07, 1.61, 1.35

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.