Can we not get around this by using randomly chosen questions? And then we have IP=PSPACE, so anything that’s in PSPACE, he can relatively quickly convince us he can solve. Obligatory Scott Aaronson link.
Thanks for that link, it was quite good. Any chance you could elaborate a bit on the IP=PSPACE identity?
No, I don’t really know complexity theory at all, so I couldn’t really tell you any more than Wikipedia could.
Current theme: default
Less Wrong (text)
Less Wrong (link)
Can we not get around this by using randomly chosen questions? And then we have IP=PSPACE, so anything that’s in PSPACE, he can relatively quickly convince us he can solve. Obligatory Scott Aaronson link.
Thanks for that link, it was quite good. Any chance you could elaborate a bit on the IP=PSPACE identity?
No, I don’t really know complexity theory at all, so I couldn’t really tell you any more than Wikipedia could.