30 ms·

What are the implications of solving the P versus NP problem? What practical effects would that have? Not trying to belittle the problem, just curious as an out

by choxi 9y ago

What are the implications of solving the P versus NP problem? What practical effects would that have? Not trying to belittle the problem, just curious as an outsider.

bottombutton 9y ago
Kind of like proving that you can't solve the halting problem, it lets us put to rest the idea that you can reduce the complexity of NP problems to a deterministic polynomial solution. The collective brainpower can be used to solve other problems.
tannhauser23 9y ago
This is a really nice list of the implications, but breaking public-key cryptography is at the top of the list: https://softwareengineering.stackexchange.com/questions/148836/what-would-be-the-impact-of-p-np https://softwareengineering.stackexchange.com/questions/1488... I should say, theoretically breaking public-key. In reality the problem may remain too hard to brute force even if the P vs NP problem is solved.
- dom0 9y ago
  > breaking This preprint "implies P not equal NP".
davewritescode 9y ago
Intuitively, almost everyone assumes that P != NP but it's been incredibly difficult to prove. If P == NP were proved it would be earth shattering, because lots of difficult problems may become solvable.
- bradleyjg 9y ago
  Is that really true though? What if someone solves does P equal NP problem by finding a polynomial time algorithm for a problem in NP, but the asymptotic run time is O(n^10^100)? Sure the race would be on to improve that, but in the meanwhile no difficult problems would become solvable.
  - jakeogh 9y ago
    related to https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/ https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...
    - bradleyjg 9y ago
      That was really entertaining, thanks for linking it. I especially liked this bit: David Johnson famously once said, For any instance {G = (V, E)} that one could fit into the known universe, one would easily prefer {|V |^{70}} to even constant time, if that constant had to be one of Robertson and Seymour’s. I was curious so I tracked down this: Johnson estimated that the hidden constant is “somewhat larger” than 2 ⇑ (2 ⇑ (2 ⇑ (h/2)) + 3), where 2 ⇑ t denotes an exponential tower of t 2s (2 ⇑ 0 = 1 and 2 ⇑ t = 2^2⇑(t−1)) and h is the number of vertices in H.
  - OJFord 9y ago
    It's generally not the case though: problems that arise 'naturally', i.e have not been constructed to counter my forthcoming point, in P seem to be of low order. If NPC problems where P in n^{10^100}, wouldn't we expect a wealth of problems between there and the myriad at n^2 or so?
    - baddox 9y ago
      Why would that be more surprising than the fact that some "natural" problems are polynomial and some are exponential, given that an exponential running time is asymptotically slower than any polynomial running time?
  - JabavuAdams 9y ago
    Often, just knowing that something is possible can be a catalyst for big advances. It's easier to get people to devote resources to a hard but solvable problem than to one which may not even be solvable.
- enriquto 9y ago
  This interpretation is wrong. The class P contains for example O(N^(10^100000!)), that are not "solvable" by any remotely reasonable meaning of the word.
  - deong 9y ago
    This is true, but it's difficult to imagine what such a problem could look like. In reality, algorithms tend to come in discrete complexity "units" with very small terms. A linear algorithm isn't just fast -- it tells you something about how such an algorithm works and thus something important about the problem it solves. A quadratic algorithm can be interpreted as a "considers all pairs from the inputs" algorithm. An n*log(n) algorithm does a divide and conquer step for each input. Moving to the exponential world, you have the 2^n "tries all combinations" and n! "tries all orderings" type algorithms, which again, make sense both as mathematical functions as well as behaviors that constitute sensible algorithms. What does an O(n^10,000) algorithm do? What understandable problem yields a solution that behaves that way?
    - DonbunEf7 9y ago
      To follow up on this, in computational linguistics, there is a sharp divide between facts which take cubic time, like recognizing whether a string belongs to a context-free language, and facts which are halting-problem-hard, like recognizing whether two context-free grammars describe the same language. There doesn't appear to be much of a middle ground. In another realm of computational mathematics, matrix mjultiplication is cubic, with optimizations that can approach quadratic time with lots of effort. It's conjectured that matrix multiplication can actually be brought arbitrarily close to quadratic time, but at the expense of ever-more-complex algorithms. It could very well be that the biggest interesting exponent in P is 3 or 4.
      - phkahler 9y ago
        The AKS algorithm has been reduced to an exponent of 6. That really strikes me as large for polynomial time algorithms though.
- wolfgke 9y ago
  > Intuitively, almost everyone assumes that P != NP Donald Knuth believes P = NP. Source: http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions http://www.informit.com/articles/article.aspx?p=2213858&WT.m... (question 17). Also cf. https://www.quora.com/Why-does-Donald-Knuth-think-that-P-NP https://www.quora.com/Why-does-Donald-Knuth-think-that-P-NP
  - Analemma_ 9y ago
    But keep in mind that he (and just about everyone who believes P = NP) thinks any proof of it will be non-constructive and that we will never actually find a polynomial-time algorithm for NP problems.
zolthrowaway 9y ago
The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security. We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this may help a academic researcher in CompSci, but it probably doesn't change much for most programmers.
- nerdponx 9y ago
  Beyond crypto, problems like the traveling salesman would also be solvable in polynomial time.
  - Govindae 9y ago
    Well... The traveling salesman decision problem, not the general case. The problem of finding the optimum path is not in NP, if I give you a candidate solution you can't easily check if it's the global optimum. What is in NP is the decision problem, finding a path that is better than a given bound. If I hand you a candidate solution, you just have to compare the sum of the distances to the bound to check it.
    - hnaccy 9y ago
      If you can solve the decision TSP in polytime you can solve the optimization case in polytime.
      - hexomancer 9y ago
        How? edit: The wikipedia mentions that the TSP problem is NP-hard and explicitly says that the decision version of this problem is NP-complete. My assumption is that if the optimization version was proven to be NP-hard there would be no need to explicitly mention the decision version. I can think of a way to use the decision version to find a solution to the optimization version but i feel like it must be flawed: First we do a binary search on `L` (the length of the tour- input to the decision version) so we can find the optimal L within a factor of epsilon (maybe this epsilon is the flaw? But I don't think that is the case.) Now we pick an edge and increase its weight to infinity. Now we do the binary search again on the new graph. If the value of the optimal solution has changed it means that the edge must be in the optimal optimization solution. By doing the same process on all the edges we can find the optimal solution. As I said there must be a flaw in the above algorithm but I can't find it.
irundebian 9y ago
Some cryptographic implications on solving the P vs. NP problem or proofing some other stuff on average case complexity: https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf
jcranmer 9y ago
In practical terms, a solution to P=NP is very likely to have absolutely no impact on our algorithms, even if the solution is that P=NP. The main utility is in our understanding of complexity theory, and a better understanding of why certain problems, and certain instances of problems, have to be hard. Let me explain why P=NP probably won't have any impact, since you see a lot of bullshit claiming lots of bad things will happen. The description of complexity classes like P and NP sweep a lot of details under the rug, and those details matter a lot of practical matters. The more important of these matters is that complexity is based on worst-case running time, not average-case or typical-case. Often times, we can solve most instances of "hard" problems. We can factor most integers, for example--half of them are divisible by 2, and another sixth divisible by 3. If we limit are inputs to factoring products of two primes of roughly equal size, that is difficult. SAT is another example: it may be the canonical NP-complete problem, but many people think nothing of using a SAT solver (or its cousin, the SMT solver) to solve for things like "how do I find an input that can reach this program point." Except if solving that condition requires, say, finding SHA256(x) = binary digits of pi. This is one of the main cruxes of P?=NP that doesn't come out much: it's not so much that problems are hard or easy, it's that there's this field of problem instances that seem to be intrinsically hard. Indeed, if you look at restricted versions of these NP-complete problems, you'll find that some restrictions still retain NP-complete, but a very slight reduction in those restrictions suddenly admits a very simple, fast, easy solution. The related notion that you see people sometimes bring up and dismiss is that P and NP hide constants. This objection tends to be dismissed because most people have no familiarity with polynomial-time algorithms with massive constants. But such algorithms do exist, and they tend to crop up in combinatorial-style algorithms. Which, incidentally, is probably what a polynomial algorithm for an NP-complete problem would be. Let me explain by analogy of a not-so-recently-solved problem that's a weaker but related notion to P?=NP, L?=SL. This question is essentially asking "could you solve every problem that's equivalent to checking for connectivity in an undirected graph using only constant memory" [1]. The answer turns out to be yes. In essence, there is a deterministic string of coin flips deciding your next vertex that will, if followed, eventually guarantee that you will hit every node in the graph that you can reach within a certain amount of time--if your graph has certain properties. And it's possible to transform every graph into one with this property by replacing every node with an expander graph that's only of size 3^2^16 at the smallest. But since the new graph is 3^2^16 * N, that large number is a constant factor that "doesn't matter". These kinds of constants show up a lot in combinatorial algorithms. All of these algorithms basically have the property that you can solve the input fairly easy if the input has some structure, but to guarantee that the input has that structure, you need to embed it in a very large instance. I argue that, if P=NP were to hold, it would have a similar form to these algorithms. We know that there are some instances that just seem to be intrinsically harder than others, and we know that there are large classes of instances that can be easily solved with fast algorithms. If we haven't been able to generalize the fast algorithms to cover the hard instances but a "fast" (ignoring constants) algorithm must exist, then the apparent complexity has to be generated from sort of fiendish complexity-multiplying, combinatoric structure. We already see in modern security algorithms that ciphers and hashes have to carefully choose their parameters to make sure they stay in a hard subset of their input algorithms. So even if P=NP, the hard subset is likely to remain much harder than the easy subset, and that gap is sufficient to maintain security. [1] A very imprecise characterization.
efm 9y ago
_The Golden Ticket_ is a non-technical book discussing the implications of solving P vs NP http://goldenticket.fortnow.com/ http://goldenticket.fortnow.com/

by choxi 9y ago

What are the implications of solving the P versus NP problem? What practical effects would that have? Not trying to belittle the problem, just curious as an outsider.

bottombutton 9y ago

Kind of like proving that you can't solve the halting problem, it lets us put to rest the idea that you can reduce the complexity of NP problems to a deterministic polynomial solution. The collective brainpower can be used to solve other problems.

tannhauser23 9y ago

This is a really nice list of the implications, but breaking public-key cryptography is at the top of the list: https://softwareengineering.stackexchange.com/questions/148836/what-would-be-the-impact-of-p-np https://softwareengineering.stackexchange.com/questions/1488... I should say, theoretically breaking public-key. In reality the problem may remain too hard to brute force even if the P vs NP problem is solved.

dom0 9y ago
> breaking This preprint "implies P not equal NP".

davewritescode 9y ago

Intuitively, almost everyone assumes that P != NP but it's been incredibly difficult to prove. If P == NP were proved it would be earth shattering, because lots of difficult problems may become solvable.

bradleyjg 9y ago
Is that really true though? What if someone solves does P equal NP problem by finding a polynomial time algorithm for a problem in NP, but the asymptotic run time is O(n^10^100)? Sure the race would be on to improve that, but in the meanwhile no difficult problems would become solvable.
- jakeogh 9y ago
  related to https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/ https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...
  - bradleyjg 9y ago
    That was really entertaining, thanks for linking it. I especially liked this bit: David Johnson famously once said, For any instance {G = (V, E)} that one could fit into the known universe, one would easily prefer {|V |^{70}} to even constant time, if that constant had to be one of Robertson and Seymour’s. I was curious so I tracked down this: Johnson estimated that the hidden constant is “somewhat larger” than 2 ⇑ (2 ⇑ (2 ⇑ (h/2)) + 3), where 2 ⇑ t denotes an exponential tower of t 2s (2 ⇑ 0 = 1 and 2 ⇑ t = 2^2⇑(t−1)) and h is the number of vertices in H.
- OJFord 9y ago
  It's generally not the case though: problems that arise 'naturally', i.e have not been constructed to counter my forthcoming point, in P seem to be of low order. If NPC problems where P in n^{10^100}, wouldn't we expect a wealth of problems between there and the myriad at n^2 or so?
  - baddox 9y ago
    Why would that be more surprising than the fact that some "natural" problems are polynomial and some are exponential, given that an exponential running time is asymptotically slower than any polynomial running time?
- JabavuAdams 9y ago
  Often, just knowing that something is possible can be a catalyst for big advances. It's easier to get people to devote resources to a hard but solvable problem than to one which may not even be solvable.
enriquto 9y ago
This interpretation is wrong. The class P contains for example O(N^(10^100000!)), that are not "solvable" by any remotely reasonable meaning of the word.
- deong 9y ago
  This is true, but it's difficult to imagine what such a problem could look like. In reality, algorithms tend to come in discrete complexity "units" with very small terms. A linear algorithm isn't just fast -- it tells you something about how such an algorithm works and thus something important about the problem it solves. A quadratic algorithm can be interpreted as a "considers all pairs from the inputs" algorithm. An n*log(n) algorithm does a divide and conquer step for each input. Moving to the exponential world, you have the 2^n "tries all combinations" and n! "tries all orderings" type algorithms, which again, make sense both as mathematical functions as well as behaviors that constitute sensible algorithms. What does an O(n^10,000) algorithm do? What understandable problem yields a solution that behaves that way?
  - DonbunEf7 9y ago
    To follow up on this, in computational linguistics, there is a sharp divide between facts which take cubic time, like recognizing whether a string belongs to a context-free language, and facts which are halting-problem-hard, like recognizing whether two context-free grammars describe the same language. There doesn't appear to be much of a middle ground. In another realm of computational mathematics, matrix mjultiplication is cubic, with optimizations that can approach quadratic time with lots of effort. It's conjectured that matrix multiplication can actually be brought arbitrarily close to quadratic time, but at the expense of ever-more-complex algorithms. It could very well be that the biggest interesting exponent in P is 3 or 4.
    - phkahler 9y ago
      The AKS algorithm has been reduced to an exponent of 6. That really strikes me as large for polynomial time algorithms though.
wolfgke 9y ago
> Intuitively, almost everyone assumes that P != NP Donald Knuth believes P = NP. Source: http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions http://www.informit.com/articles/article.aspx?p=2213858&WT.m... (question 17). Also cf. https://www.quora.com/Why-does-Donald-Knuth-think-that-P-NP https://www.quora.com/Why-does-Donald-Knuth-think-that-P-NP
- Analemma_ 9y ago
  But keep in mind that he (and just about everyone who believes P = NP) thinks any proof of it will be non-constructive and that we will never actually find a polynomial-time algorithm for NP problems.

zolthrowaway 9y ago

The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security. We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this may help a academic researcher in CompSci, but it probably doesn't change much for most programmers.

nerdponx 9y ago
Beyond crypto, problems like the traveling salesman would also be solvable in polynomial time.
- Govindae 9y ago
  Well... The traveling salesman decision problem, not the general case. The problem of finding the optimum path is not in NP, if I give you a candidate solution you can't easily check if it's the global optimum. What is in NP is the decision problem, finding a path that is better than a given bound. If I hand you a candidate solution, you just have to compare the sum of the distances to the bound to check it.
  - hnaccy 9y ago
    If you can solve the decision TSP in polytime you can solve the optimization case in polytime.
    - hexomancer 9y ago
      How? edit: The wikipedia mentions that the TSP problem is NP-hard and explicitly says that the decision version of this problem is NP-complete. My assumption is that if the optimization version was proven to be NP-hard there would be no need to explicitly mention the decision version. I can think of a way to use the decision version to find a solution to the optimization version but i feel like it must be flawed: First we do a binary search on `L` (the length of the tour- input to the decision version) so we can find the optimal L within a factor of epsilon (maybe this epsilon is the flaw? But I don't think that is the case.) Now we pick an edge and increase its weight to infinity. Now we do the binary search again on the new graph. If the value of the optimal solution has changed it means that the edge must be in the optimal optimization solution. By doing the same process on all the edges we can find the optimal solution. As I said there must be a flaw in the above algorithm but I can't find it.

irundebian 9y ago

Some cryptographic implications on solving the P vs. NP problem or proofing some other stuff on average case complexity: https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf

jcranmer 9y ago

In practical terms, a solution to P=NP is very likely to have absolutely no impact on our algorithms, even if the solution is that P=NP. The main utility is in our understanding of complexity theory, and a better understanding of why certain problems, and certain instances of problems, have to be hard. Let me explain why P=NP probably won't have any impact, since you see a lot of bullshit claiming lots of bad things will happen. The description of complexity classes like P and NP sweep a lot of details under the rug, and those details matter a lot of practical matters. The more important of these matters is that complexity is based on worst-case running time, not average-case or typical-case. Often times, we can solve most instances of "hard" problems. We can factor most integers, for example--half of them are divisible by 2, and another sixth divisible by 3. If we limit are inputs to factoring products of two primes of roughly equal size, that is difficult. SAT is another example: it may be the canonical NP-complete problem, but many people think nothing of using a SAT solver (or its cousin, the SMT solver) to solve for things like "how do I find an input that can reach this program point." Except if solving that condition requires, say, finding SHA256(x) = binary digits of pi. This is one of the main cruxes of P?=NP that doesn't come out much: it's not so much that problems are hard or easy, it's that there's this field of problem instances that seem to be intrinsically hard. Indeed, if you look at restricted versions of these NP-complete problems, you'll find that some restrictions still retain NP-complete, but a very slight reduction in those restrictions suddenly admits a very simple, fast, easy solution. The related notion that you see people sometimes bring up and dismiss is that P and NP hide constants. This objection tends to be dismissed because most people have no familiarity with polynomial-time algorithms with massive constants. But such algorithms do exist, and they tend to crop up in combinatorial-style algorithms. Which, incidentally, is probably what a polynomial algorithm for an NP-complete problem would be. Let me explain by analogy of a not-so-recently-solved problem that's a weaker but related notion to P?=NP, L?=SL. This question is essentially asking "could you solve every problem that's equivalent to checking for connectivity in an undirected graph using only constant memory" [1]. The answer turns out to be yes. In essence, there is a deterministic string of coin flips deciding your next vertex that will, if followed, eventually guarantee that you will hit every node in the graph that you can reach within a certain amount of time--if your graph has certain properties. And it's possible to transform every graph into one with this property by replacing every node with an expander graph that's only of size 3^2^16 at the smallest. But since the new graph is 3^2^16 * N, that large number is a constant factor that "doesn't matter". These kinds of constants show up a lot in combinatorial algorithms. All of these algorithms basically have the property that you can solve the input fairly easy if the input has some structure, but to guarantee that the input has that structure, you need to embed it in a very large instance. I argue that, if P=NP were to hold, it would have a similar form to these algorithms. We know that there are some instances that just seem to be intrinsically harder than others, and we know that there are large classes of instances that can be easily solved with fast algorithms. If we haven't been able to generalize the fast algorithms to cover the hard instances but a "fast" (ignoring constants) algorithm must exist, then the apparent complexity has to be generated from sort of fiendish complexity-multiplying, combinatoric structure. We already see in modern security algorithms that ciphers and hashes have to carefully choose their parameters to make sure they stay in a hard subset of their input algorithms. So even if P=NP, the hard subset is likely to remain much harder than the easy subset, and that gap is sufficient to maintain security. [1] A very imprecise characterization.

efm 9y ago

_The Golden Ticket_ is a non-technical book discussing the implications of solving P vs NP http://goldenticket.fortnow.com/ http://goldenticket.fortnow.com/