Two queries
Harry Buhrman, Lance Fortnow · Conference on Computational Complexity · 1998
We consider the question whether two queries to SAT are as powerful as one query. We show that if P/sup NP[1]/=P/sup NP[2]/ then; locally either NP=coNP or NP has polynomial-size circuits; P/sup NP/=P/sup NP[1]/; /spl Sigma//sub 2//sup p/=UP/sup NP[1]//spl cap/RP/sup NP[1]/; PH=BPP/sup NP[1]/. Moreover we extend work of E. Hemaspaandra et al. (1997) to show that if P(/spl Sigma//sub 2//sup p/[1])=P(/spl Sigma//sub 2//sup p/[2]) then /spl Sigma//sub 2//sup p/=/spl Pi//sub 2//sup p/. We also give a relativized world where P/sup NP[1]/=P/sup NP[2]/ but NP/spl ne/coNP.