3
$\begingroup$

Let ${\tt QH}$ stand for the Query Hierarchy, defined as the union of all classes ${\tt P}^{{\tt NP}[k]}$, of problems solvable by polynomial time machines making at most $k$ queries to ${\tt NP}$ and ${\tt PH}$ stand for the Polynomial time hierarchy. In $1988$ Kadin proved that, if the ${\tt QH}$ collapses, so does ${\tt PH}$ (here). Is this sort of result known for other hierarchies?

To make my question more precise, let $\mathcal{C}$ and $\mathcal{D}$ be two complexity classes, let ${\tt QH}_\mathcal{C}^\mathcal{D}$ be the query hierarchy constructed by relativizng $\mathcal{C}$ to $\mathcal{D}$, but allowing, in each level of the hierarchy, only a finite number of queries to $\mathcal{D}$ to be made, and let $\mathcal{DH}$ be the hierarchy obtained by setting the first level to $\mathcal{D}$ and the successive levels as $\mathcal{D}$ with oracle access to the previous level. Are there other cases, besides considering $\mathcal{C} = {\tt P}$ and $\mathcal{D} = {\tt NP}$, where it is known that a collapse of the first hierarchy implies the collapse of the second?

I am especially interested in knowing if this has been studied the context of (poly)logarithmic time complexity. Consider the Random Access Turing Machine (RATM) model to define logarithmic time complexity classes. Does the collapse of a query hierarchy defined by allowing increasingly more queries of logarithmic time RATM to ${\tt NLOG}$ (non-deterministic logarithmic time) imply the collapse of the logarithmic hierarchy? As it is known that the latter does not collapse (a result of Sipser here), this would imply that nor does the first.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.