Thursday, February 26, 2015

Selecting the Correct Oracle

After my post last week on the Complexity accepts, a friend of Shuichi Hirahara send Shuichi an email saying that I was interested in his paper. Shuichi contacted me, sent me his paper and we had a few good emails back and forth. He posted his paper Identifying an Honest EXPNP 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 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?

1 comment:

  1. I am an academic computer scientist. I am not a theoretician, but take pride in keeping myself abreast of the latest developments in TCS.

    Yet, 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: