We consider the question whether two queries SAT are as powerful as one query. We show that if P~NP[1] = P~NP[2] then: Locally either NP = coNP or NP has polynomial-size circuits; P~NP = P~NP[ 1 ], ∑_2~p is contained in ∏_2~p/1;∑_2~p = UP~NP[ 1]⌒ RP~NP[1]; PH = BPP~NP[1]. Moreover, we extend the work of Hemaspaandra, Hemaspaandra, and Hempel to show that if P~∑(_2~p)[1] = P~∑(_2~p)[2] then ∑-2~p = ∏_2~p. We also give a relativized world, where P~NP[1] = P~NP[2], but NP ≠coNP.
展开▼
