Hacker News Reader

Comment by magneticnorth | Hacker News Reader

The discussion of this paper on Scott Aaronson's blog is a great way to get a bit deeper into what was proved and what the implications are: https://www.scottaaronson.com/blog/?p=4512

View on HN

Thank goodness. I don't want to be mean but the originally linked article was badly written. Eg. A sentence about the halting problem being unsolvable with a follow on sentence to that opening up that everything could be solved by computers...

I noticed the same error you did, and I agree the OP article doesn't tell us much about why this result is important, but I actually thought the OP article did a better job of explaining complexity classes at an extremely elementary level (not relying on what a polynomial is) than other articles I've seen

Agreed - the original article is written well enough that I got very interested in the result, but not well enough that I came away with much of an understanding of what, really, was proved and what all the important implications are.

>> There is a protocol by which two entangled provers can convince a polynomial-time verifier of the answer to any computable problem whatsoever (!!), or indeed that a given Turing machine halts. Sounds like an existence proof rather than an actual algorithm. Still interesting even if it take a computer the size of the earth.

I'm also puzzled by the use of the word "convince" in there. Is it possible for such a quantum oracle to lie?

Convince means the verifier can prove to itself what the provers are telling it in polynomial time, without trusting the provers.

It's still unclear whether the algorithm the verifier uses has actually been identified or has only been proven to exist.

>> Still interesting even if it take a computer the size of the earth.

There are some white mice on Magrathea who hold the IP on this.

That sounds like a probabilistically verifiable proof. See http://people.csail.mit.edu/madhu/papers/2009/pcpcacm.pdf for more.

Reply on news.ycombinator.com