4 ms·

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

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 https://www.scottaaronson.com/blog/?p=4512

AnotherGoodName 6y ago
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...
- deleted 6y ago
  [deleted]
- magneticnorth 6y ago
  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.
- jessriedel 6y ago
  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
phkahler 6y ago
>> 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?
- terrelln 6y ago
  Convince means the verifier can prove to itself what the provers are telling it in polynomial time, without trusting the provers.
  - jessriedel 6y ago
    It's still unclear whether the algorithm the verifier uses has actually been identified or has only been proven to exist.
- steve_gh 6y ago
  >> 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.
- btilly 6y ago
  That sounds like a probabilistically verifiable proof. See http://people.csail.mit.edu/madhu/papers/2009/pcpcacm.pdf http://people.csail.mit.edu/madhu/papers/2009/pcpcacm.pdf for more.

AnotherGoodName 6y ago

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

deleted 6y ago
[deleted]
magneticnorth 6y ago
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.
jessriedel 6y ago
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

phkahler 6y ago

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

terrelln 6y ago
Convince means the verifier can prove to itself what the provers are telling it in polynomial time, without trusting the provers.
- jessriedel 6y ago
  It's still unclear whether the algorithm the verifier uses has actually been identified or has only been proven to exist.
steve_gh 6y ago
>> 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.
btilly 6y ago
That sounds like a probabilistically verifiable proof. See http://people.csail.mit.edu/madhu/papers/2009/pcpcacm.pdf http://people.csail.mit.edu/madhu/papers/2009/pcpcacm.pdf for more.