5 ms·

One of the points of Scott Aaronson's excellent "Quantum Computing since Democritus" is that if you can quickly solve NP problems, you basically have super powe

by tgb 11y ago

One of the points of Scott Aaronson's excellent "Quantum Computing since Democritus" is that if you can quickly solve NP problems, you basically have super powers. Forget about SAT or Travelling Salesman, you can now do fast automated theorem provers and the like. Depending on how it were solved, you wouldn't read about P=NP on arxiv, you'd read about someone making billions on the stock market. Aaronson describes it as being comparably implausible to having faster than light communication. If this paper is true, then it looks to me like quantum computers would be a means of doing that. I'm skeptical. Know those sci-fi stories where they hand-wave a quantum computer to have infinite computing power? Then they simulate the universe or hack all the computers simultaneously or whatever. That's all a laughable misinterpretation of what current state-of-the-art quantum algorithms can do (even if we remove the technical details of constructing the machine). Well, if this paper holds up, then that's a whole lot closer to the truth, maybe! (Disclaimer: not an expert. I really hope to see Aaronson's analysis of this soon.)

Rauchg 11y ago
It's worth pointing out that they already claim to have proven NP ⊆ BQP > The common belief concerning the relationship between NP and BQP was that NP is not contained in BQP (e.g see chapter 15 of [8]. However, a recent paper by one of the current authors has shown that an NP-hard problem (Graph Bisection) can be efficiently solved, with low failure probability, by a quantum algorithm [13]. This implies that NP is in fact contained within BQP, as any NP problem can be polynomially reduced to an NP-hard problem
- jsprogrammer 11y ago
  >any NP problem can be polynomially reduced to an NP-hard problem Except that there is some probability that the algorithm will be unable to solve the problem?
  - eru 11y ago
    Success/Failure would be independent between runs. Ie if you fail, you just run again.
JacobEdelman 11y ago
At this point I feel bad for Scott Aaronson. Everytime a crackpot paper comes out (and I'm 97% convinced at this point this is one of them) he takes the time to refute it on his blog.
lojack 11y ago
If I'm not mistaken, showing P=NP doesn't necessarily guarantee that the solution is quick and likewise being able to quickly solve NP problems doesn't require showing that P=NP.
- sacado2 11y ago
  Depends on how you define "quick". But, sure, finding an algorithm that solves SAT in O(1.0000001^n) (still exponential) would be much better in practice than finding one that would solve it in O(n^100) (although polynomial).
sacado2 11y ago
You could very well have P = NP but not have superpowers yet. There are problems which are significantly harder than SAT et al. The canonical one for PSPACE (which is a superset of NP) is QBF (which is only SAT on steroids, i.e SAT + universal quantifier). For instance, while SAT can be used to model one-player games (sudoku, 8 queens, etc.), you need QBF to model two-player games (even tic-tac-toe). And stock market looks a lot like a n-players game. So, unless NP = PSPACE, even with P = NP you're stuck with limited superpowers.
- c_lebesgue 11y ago
  Nitpick: you need a potentially unbounded number of alternations between existential and universal quantifiers to get PSPACE. Otherwise it is just somewhere in the polynomial hierarchy. Otherwise you are right, "outsmarting" the rest of the world is probably in PSPACE.
abecedarius 11y ago
This is all true, except nobody has a large quantum computer yet. You could discover an efficient SAT algorithm and not be able to apply it for years or decades. (I don't expect this either.)
coliveira 11y ago
> if you can quickly solve NP problems, you basically have super powers. This classic argument is flawed, because P=NP doesn't mean that you can "easily" solve all NP problems. Nature is still free to define huge exponents to difficult problems, making them essentially unsolvable in practice. I even heard Knuth recognizing this recently.
- tgb 11y ago
  Yes, of course, in the same sense that we might have faster than light communication (but just barely) and not be able to exploit it for meaningful communication backwards in time to make a killing on the stock market. But we can still think "wow, that sounds kind of absurd" as a metric by which to judge the likelihood of a result. Either way, this is Scott Aaronson's argument, not mine. For example, he makes it here: http://www.scottaaronson.com/writings/limitsqc-draft.pdf http://www.scottaaronson.com/writings/limitsqc-draft.pdf
  - coliveira 11y ago
    People like Scott Aaronson who spouse this view use it as a fundamental reason why NP=P should be false. The problem is exactly that it is a flawed argument. It could be an argument for the impossibility of finding "efficient" algorithms, but this is not what P=NP is about. For all we know, some problems in P could be so difficult as to preclude any practical algorithm.
    - tgb 11y ago
      That's true: it's essentially conflating "efficient" meaning in polynomial time with "efficient" in the colloquial sense. Still is enough to make me skeptical!
      - coliveira 11y ago
        I am in no way saying that this indicates that P=NP, so I am also skeptic. I am just pointing out that you should be skeptic for the right reasons, not because of a misused argument.

by tgb 11y ago

Rauchg 11y ago

It's worth pointing out that they already claim to have proven NP ⊆ BQP > The common belief concerning the relationship between NP and BQP was that NP is not contained in BQP (e.g see chapter 15 of [8]. However, a recent paper by one of the current authors has shown that an NP-hard problem (Graph Bisection) can be efficiently solved, with low failure probability, by a quantum algorithm [13]. This implies that NP is in fact contained within BQP, as any NP problem can be polynomially reduced to an NP-hard problem

jsprogrammer 11y ago
>any NP problem can be polynomially reduced to an NP-hard problem Except that there is some probability that the algorithm will be unable to solve the problem?
- eru 11y ago
  Success/Failure would be independent between runs. Ie if you fail, you just run again.

JacobEdelman 11y ago

At this point I feel bad for Scott Aaronson. Everytime a crackpot paper comes out (and I'm 97% convinced at this point this is one of them) he takes the time to refute it on his blog.

lojack 11y ago

If I'm not mistaken, showing P=NP doesn't necessarily guarantee that the solution is quick and likewise being able to quickly solve NP problems doesn't require showing that P=NP.

sacado2 11y ago
Depends on how you define "quick". But, sure, finding an algorithm that solves SAT in O(1.0000001^n) (still exponential) would be much better in practice than finding one that would solve it in O(n^100) (although polynomial).

sacado2 11y ago

You could very well have P = NP but not have superpowers yet. There are problems which are significantly harder than SAT et al. The canonical one for PSPACE (which is a superset of NP) is QBF (which is only SAT on steroids, i.e SAT + universal quantifier). For instance, while SAT can be used to model one-player games (sudoku, 8 queens, etc.), you need QBF to model two-player games (even tic-tac-toe). And stock market looks a lot like a n-players game. So, unless NP = PSPACE, even with P = NP you're stuck with limited superpowers.

c_lebesgue 11y ago
Nitpick: you need a potentially unbounded number of alternations between existential and universal quantifiers to get PSPACE. Otherwise it is just somewhere in the polynomial hierarchy. Otherwise you are right, "outsmarting" the rest of the world is probably in PSPACE.

abecedarius 11y ago

This is all true, except nobody has a large quantum computer yet. You could discover an efficient SAT algorithm and not be able to apply it for years or decades. (I don't expect this either.)

coliveira 11y ago

> if you can quickly solve NP problems, you basically have super powers. This classic argument is flawed, because P=NP doesn't mean that you can "easily" solve all NP problems. Nature is still free to define huge exponents to difficult problems, making them essentially unsolvable in practice. I even heard Knuth recognizing this recently.

tgb 11y ago
Yes, of course, in the same sense that we might have faster than light communication (but just barely) and not be able to exploit it for meaningful communication backwards in time to make a killing on the stock market. But we can still think "wow, that sounds kind of absurd" as a metric by which to judge the likelihood of a result. Either way, this is Scott Aaronson's argument, not mine. For example, he makes it here: http://www.scottaaronson.com/writings/limitsqc-draft.pdf http://www.scottaaronson.com/writings/limitsqc-draft.pdf
- coliveira 11y ago
  People like Scott Aaronson who spouse this view use it as a fundamental reason why NP=P should be false. The problem is exactly that it is a flawed argument. It could be an argument for the impossibility of finding "efficient" algorithms, but this is not what P=NP is about. For all we know, some problems in P could be so difficult as to preclude any practical algorithm.
  - tgb 11y ago
    That's true: it's essentially conflating "efficient" meaning in polynomial time with "efficient" in the colloquial sense. Still is enough to make me skeptical!
    - coliveira 11y ago
      I am in no way saying that this indicates that P=NP, so I am also skeptic. I am just pointing out that you should be skeptic for the right reasons, not because of a misused argument.