3 ms·

> First, even the CS's nightmare (where P=NP) may mean little practical difference (e.g. the simplest 'NP' takes O(n^1000)). Sure, it may. But there are precio

> First, even the CS's nightmare (where P=NP) may mean little practical difference (e.g. the simplest 'NP' takes O(n^1000)). Sure, it may. But there are precious few examples in the wild where we're dealing with crazy powers like that. I think the bigger (but still quite small) failure in P's ability to measure "ease" of computation is that it only considers the worst case. A good example is graph isomorphism. There was recently a development of a quasipolynomial algorithm for graph isomorphism, which had the best bound we've found for the problem yet. However, with our existing algorithms it was extremely difficult to find examples where they didn't run in polynomial time, even when actively looking for them. But again, this is the exception, not the rule. > Second, for many problems even O(n^2) is too much (think of big data problems). (Also, given that computation requires physical resources, you cannot scale it arbitrarily.) So even in P the actual exponent matters a lot. Very true, but TCS spends a lot of time developing new algorithms to shrink exponents as well. A lot of the methods and skills needed for making better algorithms to get problems into P also apply to moving them around within P. And many of the same tactics for trying to figure out exactly how P and NP fit together apply to trying to figure out the same for P and BQP. Since you have a background in quantum physics and (I assume) care about that field, are you aware that quite a bit of the TCS community works on quantum problems? There have been plenty of results that stand to be very physically relevant. Some good examples are the recent (quite rapid) progress in analyzing symmetric cryptography schemes' vulnerability to attacks by a quantum computers[1]. Interestingly, many are starting from the same jumping off that asymmetric attacks did; namely Simon's algorithm (an important stepping stone towards Shor's algorithm). [1]: https://arxiv.org/abs/1602.05973 https://arxiv.org/abs/1602.05973

stared 10y ago
Don't take me wrong - TCS is an important discipline, with both interesting practical and theoretical results. The only thing I am criticizing here is the _metaphysical_ implications of computational complexity classes (and also, jargon which is misleading for not TCS people - e.g. O(n^100) s not "efficient" or "fast"). Furthermore, as you pointed, some problems have practical solutions which usually work efficiently, even if not always or give approximate, but still - useful, solution. > There have been plenty of results that stand to be very physically relevant What I meant was not "can be applied to physical systems" (I agree!), but "is a foundation for physical laws" (I am highly skeptical and I am yet to see an example). (Though, to be honest, I was more in quantum info that quantum computing; and right now I am more into... quantum JavaScript: http://quantumgame.io/ http://quantumgame.io/)
- ekidd 10y ago
  In practice, n^100 is not a thing that happens except in weird or contrived cases. n^2 is common. n^3 turns up here and there. I've heard of n^5 in graph algorithms, I think, but it's pretty exotic. Let's see if I can provide a very rudimentary intuition about why this might happen. YMMV, and I'm sure this isn't the whole story. O(n^2) basically implies that we have to look at every pairwise combination of elements. Higher powers might imply needing to look at combinations of multiple elements / paths / whatever. In practice, these algorithms tend to be more or less tractable. O(2^n), on the other hand, generally implies a brute force search, where we need to consider every possible solution, or every possible combination of elements. This is essentially the same as saying we can't do much better than guesswork. So O(n^k) versus O(2^n) is basically "looking at small groups of elements of known size" versus "trying every possible solution." This isn't the whole story—there are problems in between the two groups, though a couple of big ones have been reduced to polynomial time in recent years. But to understand the "metaphysical" interpretations that some CS people sometimes loosely apply to the two classes, it helps to look at the actual distribution of real world algorithms. It's pretty clumpy. There's an empirical element here.
  - stared 10y ago
    High exponents happen - vide http://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant http://cstheory.stackexchange.com/questions/6660/polynomial-... for an example of O(n^79) (sic!).
    - johncolanduoni 10y ago
      Yes, but since such examples are far from common (look at all the TCS people's jaws dropping at that constant and power) I fail to see how this implies N vs NP is irrelevant except in platonic math fairytale land. Since you said you have a QI background, I'm guessing you're familiar with Landau's symmetry breaking framework for identifying phase transitions. Like P, it works perfectly in a lot of cases and substantiates our desired qualitative idea (phase transitions) with a quantitive property. However, as I'm sure you know, we've found plenty of cases in the realm of QI where it fails to identify phase transitions (e.g. topological order) that we would like to categorize as such. However, nobody would think of throwing it out entirely just because of these exceptions, since it is useful in the vast majority of cases. Such is the case with P and the notion of being "easy" to compute. Yes, some algorithms in P are actually qualitatively "hard" and some outside are actually qualitatively "easy". But in the vast majority cases, finding that a problem is in P means we've drastically reduced its difficulty, and proofs that a problem isn't in P establish bounds that make it unfeasible in the general case.

stared 10y ago

Don't take me wrong - TCS is an important discipline, with both interesting practical and theoretical results. The only thing I am criticizing here is the _metaphysical_ implications of computational complexity classes (and also, jargon which is misleading for not TCS people - e.g. O(n^100) s not "efficient" or "fast"). Furthermore, as you pointed, some problems have practical solutions which usually work efficiently, even if not always or give approximate, but still - useful, solution. > There have been plenty of results that stand to be very physically relevant What I meant was not "can be applied to physical systems" (I agree!), but "is a foundation for physical laws" (I am highly skeptical and I am yet to see an example). (Though, to be honest, I was more in quantum info that quantum computing; and right now I am more into... quantum JavaScript: http://quantumgame.io/ http://quantumgame.io/)

ekidd 10y ago
In practice, n^100 is not a thing that happens except in weird or contrived cases. n^2 is common. n^3 turns up here and there. I've heard of n^5 in graph algorithms, I think, but it's pretty exotic. Let's see if I can provide a very rudimentary intuition about why this might happen. YMMV, and I'm sure this isn't the whole story. O(n^2) basically implies that we have to look at every pairwise combination of elements. Higher powers might imply needing to look at combinations of multiple elements / paths / whatever. In practice, these algorithms tend to be more or less tractable. O(2^n), on the other hand, generally implies a brute force search, where we need to consider every possible solution, or every possible combination of elements. This is essentially the same as saying we can't do much better than guesswork. So O(n^k) versus O(2^n) is basically "looking at small groups of elements of known size" versus "trying every possible solution." This isn't the whole story—there are problems in between the two groups, though a couple of big ones have been reduced to polynomial time in recent years. But to understand the "metaphysical" interpretations that some CS people sometimes loosely apply to the two classes, it helps to look at the actual distribution of real world algorithms. It's pretty clumpy. There's an empirical element here.
- stared 10y ago
  High exponents happen - vide http://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant http://cstheory.stackexchange.com/questions/6660/polynomial-... for an example of O(n^79) (sic!).
  - johncolanduoni 10y ago
    Yes, but since such examples are far from common (look at all the TCS people's jaws dropping at that constant and power) I fail to see how this implies N vs NP is irrelevant except in platonic math fairytale land. Since you said you have a QI background, I'm guessing you're familiar with Landau's symmetry breaking framework for identifying phase transitions. Like P, it works perfectly in a lot of cases and substantiates our desired qualitative idea (phase transitions) with a quantitive property. However, as I'm sure you know, we've found plenty of cases in the realm of QI where it fails to identify phase transitions (e.g. topological order) that we would like to categorize as such. However, nobody would think of throwing it out entirely just because of these exceptions, since it is useful in the vast majority of cases. Such is the case with P and the notion of being "easy" to compute. Yes, some algorithms in P are actually qualitatively "hard" and some outside are actually qualitatively "easy". But in the vast majority cases, finding that a problem is in P means we've drastically reduced its difficulty, and proofs that a problem isn't in P establish bounds that make it unfeasible in the general case.