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?
This thread is for the discussion of Less Wrong topics that have not appeared in recent posts. If a discussion gets unwieldy, celebrate by turning it into a top-level post.
This thread brought to you by quantum immortality.