3 ms·
>> 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
by 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 agoConvince means the verifier can prove to itself what the provers are telling it in polynomial time, without trusting the provers.
- jessriedel 6y agoIt'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 agoThat 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.