^{NP}Oracle Among Many on the arXiv yesterday.

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 S

_{2}^{EXP}, the exponential analogue of S_{2}^{P}. His main theorem shows that EXP^{NP}-complete sets have this property. His proof is quite clever, using the EXP^{NP}-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 EXP

^{NP}and S_{2}^{EXP}. Is there a selector for Promise-S_{2}^{EXP}-complete languages?