5 ms·

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 lot

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.

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.