Shuichi asks the following question: Given two oracles both claiming to compute a language L, figure out which oracle is correct. For which languages does there exist such a selector?
For deterministic polynomial-time selectors, every such L must sit in PSPACE and all PSPACE-complete languages have selectors. The question gets much more interesting if you allow probabilistic computation.
Shuichi shows that every language that has a probabilistically poly-time selector sits in S2EXP, the exponential analogue of S2P. His main theorem shows that EXPNP-complete sets have this property. His proof is quite clever, using the EXPNP-complete problem of finding the lexicographically least witness of a succinctly-described exponential-size 3-SAT question. He uses PCP techniques to have each oracle produce a witness and then he has a clever way to doing binary search to find the least bit where these witnesses differ. I haven't checked all the details carefully but the proof ideas look good.
Still leaves an interesting gap between EXPNP and S2EXP. Is there a selector for Promise-S2EXP-complete languages?