What might really happen if P=NP?

Viliam Furik · 2021-05-30, 22:45

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⁶) and find a solution in O(n¹²) - 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:

Originally Posted by Viliam Furik

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.

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:

Originally Posted by mathwiz

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

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:

Originally Posted by retina

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.

chalsall · 2021-05-31, 19:24

Quote:

Originally Posted by Viliam Furik

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.

2021-05-30, 22:45	#1
Viliam Furik "Viliam Furík" Jul 2018 Martin, Slovakia 2×3×5×19 Posts	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⁶) and find a solution in O(n¹²) - 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?

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

2021-05-30, 23:09	#3
Viliam Furik "Viliam Furík" Jul 2018 Martin, Slovakia 2·3·5·19 Posts	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.

2021-05-30, 23:18	#4
mathwiz Mar 2019 2·89 Posts	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.

2021-05-30, 23:40	#6
retina Undefined "The unspeakable one" Jun 2006 My evil lair 14064₈ Posts	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.