I am wondering if hypothesis such as Strong Exponential Time Hypothesis (SETH) have been studied for problems being in a higher level of the polynomial hierarchy when we give the machine access to an oracle.

More precisely, I am interested in hypothesis of the form:

$H_k$: For all $\varepsilon < 1$, QBF cannot be solved in time $2^{\varepsilon n}$ with a machine having oracle access to a problem of $\Sigma_k$, where the oracle can be called only on polynomial-size instances (calling an oracle on non-polynomial-size inputs looks way too powerful to be reasonable).

Is there any evidence to support $H_k$ (or $\neg H_k$)? More precisely, is it known if such hypothesis is comparable to SETH somehow?

I have not found any mention of this kind of hypothesis in the literature. The only hypothesis that I have found so-far are:

I am also aware of Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity by Rahul Santhanam and Ryan Williams where it is proven that improvement on the complexity of QBF implies strong circuit lower bounds but their results cannot be applied directly to $H_k$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.