Comment by tgb | Hacker News Reader

Comment by tgb | Hacker News Reader

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.)

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.

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.

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

>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?

Success/Failure would be independent between runs. Ie if you fail, you just run again.

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.

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.

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).

> 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.

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

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.

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!

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.

> For all we know, some problems in P could be so difficult as to preclude any practical algorithm.

You can actually prove that given any (concrete) subclass of P that there is a language in both in P and harder, by a simple application of the time hierarchy theorem.

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.)

Reply on news.ycombinator.com