Practical effects if it is proved that P=NP

  • Context: Graduate 
  • Thread starter Thread starter sid_galt
  • Start date Start date
  • Tags Tags
    Effects Practical
Click For Summary

Discussion Overview

The discussion revolves around the potential practical effects of proving that P=NP, particularly in relation to NP-complete problems such as Boolean SAT, Traveling Salesman, and scheduling. Participants explore the implications of finding efficient polynomial time algorithms for these problems and the impact on fields like cryptography and algorithmic efficiency.

Discussion Character

  • Exploratory
  • Debate/contested
  • Technical explanation

Main Points Raised

  • Some participants question whether proving P=NP would lead to significant practical effects, given that approximate algorithms already perform well in many cases.
  • Others suggest that a low polynomial time solution to NP-complete problems could have substantial implications, particularly in scheduling.
  • There is a contention regarding the efficiency of algorithms for primality testing, with some asserting that primality testing is efficient while others argue it is hard, particularly in the context of integer factorization.
  • One participant notes that even if P=NP, a solution with high polynomial time complexity (e.g., O(n^100)) may not be practically useful with current technology.
  • Some participants highlight that if P=NP, it might allow for efficient generation of proofs for statements.
  • There is mention of the potential for efficiently cheating in NP-complete games like minesweeper and sudoku, although concerns are raised about the scalability and reliability of such algorithms as problem size increases.

Areas of Agreement / Disagreement

Participants express differing views on the implications of P=NP, particularly regarding the efficiency of algorithms for primality testing and the practical effects of proving P=NP. No consensus is reached on the significance of these implications.

Contextual Notes

Some discussions reference the Riemann Hypothesis and its implications for primality testing, indicating that assumptions and historical context may influence current understanding. The scalability of polynomial algorithms and their reliability as problem sizes increase remains an open question.

sid_galt
Messages
503
Reaction score
1
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)?
 
Last edited:
Mathematics news on Phys.org
One thing it can answer is that there is no efficient algorithm for primality testing.
 
Kummer said:
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.
 
NateTG said:
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.
 
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.
 
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.
 
Kummer said:
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.
 
Last edited by a moderator:
Primality testing is in P, independently of the RH, it was shown recentely i think (2003/2004?).
 
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.
 
  • #10
-Job- said:
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... :smile:
 

Similar threads

Undergrad Are electrons universal problem solvers?
  • · Replies 4 ·
Replies
4
Views
1K
If P = NP, can a proof be generated / verified efficiently for a proposition?
  • · Replies 52 ·
2
Replies
52
Views
4K
What are the implications if P=NP in Artificial Intelligence?
  • · Replies 4 ·
Replies
4
Views
5K
Undergrad NP vs P - difference between veryfing and answering
  • · Replies 4 ·
Replies
4
Views
3K
Graduate Is this the Future of Mathematics?
  • · Replies 2 ·
Replies
2
Views
2K
Graduate P vs NP Guessing and process of elimination
  • · Replies 6 ·
Replies
6
Views
2K
Graduate Consult: NP=P and P (3-SAT) - Is It Well Known?
  • · Replies 9 ·
Replies
9
Views
2K
How to prove problem is P or NP?
  • · Replies 13 ·
Replies
13
Views
16K
Graduate The P vs. NP millennial prize problem
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Is the Subset Sum Problem Truly Solved by Generating Large Random Sets?
  • · Replies 5 ·
Replies
5
Views
3K