Practical effects if it is proved that P=NP

[sid_galt]

What would be the practical effects if it is proved that P=NP and an efficient polynomial time algorithm is found for NP-complete problems?

By practical effects, I mean the practical effects of perfectly solving the problems which have been proven to be NP-complete (like Boolean SAT, Traveling salesman, scheduling, etc.)?

Because from what I have gathered, approximate algorithms (like stochastic alogrithms for e.g.) are pretty good at finding answers close to the perfect answers and algorithms that do find perfect answers if given enough time find it in reasonable times for most cases.

So will there be significant practical effects if P=NP (aside from the fact that cryptography will become impossible)?

 

[Kummer]

One thing it can answer is that there is no efficient algorithm for primality testing.

 

[NateTG]

One thing it can answer is that there is no efficient algorithm for primality testing.

That's funny. Primality testing is very efficient. Factoring, on the other hand, is hard.

 

[Kummer]

That's funny. Primality testing is very efficient. Factoring, on the other hand, is hard.

Yes. I should have said that integer factorizations is hard.

 

[sid_galt]

Actually I meant what would be the practical effects if P is proved to be equal to NP, not the practical effects of solving the question whether P=NP.

 

[-Job-]

A result of P=NP doesn't immediately guarantee practical implications, or that cryptography will become impossible. A solution to SAT in O(n^100) is not much less intractable than O(2^n) with our current technology.

There would be many practical implications of a low polynomial time solution to SAT, with scheduling probably being the most popular one.

Also, i believe that if P=NP then we might be able to efficiently generate proofs for statements.

 

[Reverie]

One thing it can answer is that there is no efficient algorithm for primality testing.

The question in the OP asked what would be the practical implication of P=NP NOT the practical implication of P not equal to NP, but the mistake is understandable given that many researchers believe that P does not equal NP.

I imagine your post meant that if P does not equal NP, then there is no efficient algorithm for primality testing.

I don't know much about the subject, but Martin Dietzfelbinger wrote a book with the title

"PRIMES is in P"

https://www.amazon.com/dp/3540403442/?tag=pfamazon01-20

Also, in 1976, G.L. Miller wrote a paper...

"Riemann's hypothesis and tests for primality" J.CSS, 13, pg. 300-317, 1976

I believe the paper proves that Primes is in P if one assumes the Riemann Hypothesis is true. However, 1976 was a long, long time ago, and someone may have found a proof that Primes is in P without assuming the Riemann Hypothesis.

As for the OP, I don't know much about practical applications, but I'm pretty sure that quite a few applications would exist if a practical algorithm were found. Other people here can probably tell you more about the practical side of things.

 

[-Job-]

Primality testing is in P, independently of the RH, it was shown recentely i think (2003/2004?).

 

[-Job-]

BTW, there are hundreds of NP-Complete problems, including games such as minesweeper and sudoku, so if nothing else you'd be able to efficiently cheat at these games.

Some polynomial algorithms may arrive at a correct answer a percentage of the time, however, and though i haven't analyzed any such algorithms closely, they probably won't scale well. So as n goes up, p (the probability of the algorithm arriving at a correct answer) goes down. Hence, even with such an algorithm, there is an n such that the probability of obtaining a correct answer is not great, such that you have to resort to more computation.

 

[Reverie]

Primality testing is in P, independently of the RH, it was shown recentely i think (2003/2004?).

I remember something like this too... but I didn't have a source...

Nice reply with the other post... good to know that there is a guiding principle that says the algorithms don't usually scale well and the probability declines with the size of the scale...

funny... best use of advanced mathematics... cheating... :rofl: