^{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?
I am an academic computer scientist. I am not a theoretician, but take pride in keeping myself abreast of the latest developments in TCS.

ReplyDeleteYet, when I read this post, I found myself asking whether results in complexity have become so specialized that it's impossible for a person with a generic CS background to comprehend the importance of the results.

It reminded me somewhat of this post about Bobby Kleinberg, and the reasons for his switch from topology to CS: http://windowsontheory.org/2013/03/21/research-life-stories-bobby-kleinberg/