Prior results show that most bounded query hierarchies cannot contain finite gaps. For example, it is known that P_(m+1)-tt^SAT = P_m-tt^SAT implies P_btt^SAT = P_m-tt^SAT and for all sets A

• FP_(m+1)-tt^A = FP_m-tt^A implies FP_btt^A = FP_m-tt^A
• P_(m+1)-T^A = P_m-T^A implies P_bT^A = ... more >>>

A language is called k-membership comparable if there exists a polynomial-time algorithm that excludes for any k words one of the 2^k possibilities for their characteristic string. It is known that all membership comparable languages can be reduced to some P-selective language with polynomially many adaptive queries. We show however ... more >>>

The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $\P^\numP$ relies on the fact that, under mild technical conditions on the complexity class $\mathcal{C}$, we have $\exists \,\mathcal{C} \subset \BP \cdot \oplus \,\mathcal{C}$. More concretely, there is a randomized reduction which transforms nonempty sets and the ... more >>>

Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with ``mild hardness'' under any P-samplable distribution H; ... more >>>