Let me denote by $\Sigma_i^P$ be a class from i-th level of polynomial time hierarchy (see eg. PH).

I'm interested in the following type of a Turing Machine $\mathcal{M}$:

  • $\mathcal{M}$ is nondeterministic
  • For an input word $w$ of length $n$, a running time of $\mathcal{M}$ is $2^{O(n)}$
  • When an input word $w$ of a length $n$ is given to $\mathcal{M}$, a machine can call an oracle in $\Sigma_n^P$ (it is important that it is the same $n$ as in the input!).

Note that if an oracle in the definition above will be from $\Sigma_k^P$ for some fixed $k$,then we will get we will get a class $\Sigma_k^{EXP}$ - the k-th level of Exponential Time Hierarchy EXPH. Also it is easy to see that presented machine works in ExpSpace.

Do you know any other characterization of such machine? Is any problem complete for this class? Any references?

  • $\begingroup$ As far as I can see, this class is more or less alternating time $O(2^n)$ with $n$ alternations. $\endgroup$ – Emil Jeřábek Jun 15 '18 at 22:38
  • $\begingroup$ In case of a fixed k it should be STA(*, 2^n, k), so the class you mentioned. However it is not clear to me what happens if a number of alternations depends on the lenght of the input. $\endgroup$ – Bartosz Bednarczyk Jun 15 '18 at 23:02
  • $\begingroup$ The problem is not well defined. Unless you intend the class to be nonuniform, the machine can only have access to a single oracle, whose inputs are somehow parameterized by $n$. But under the most natural reading that the oracle, having also access to the original input, is supposed to be computable in alternating polynomial time (in terms of the length of the whole oracle input) with at most $n$ alternations (where $n$ is the length of the original input), your class is exactly $STA(*,2^{O(n)},n)$, and its closure under poly-time reductions is $STA(*,2^{n^{O(1)}},n^{O(1)})$. $\endgroup$ – Emil Jeřábek Jun 16 '18 at 9:05
  • $\begingroup$ Well, there are some off-by-one errors in the above comment, but that's a minor difference. $\endgroup$ – Emil Jeřábek Jun 16 '18 at 9:08
  • $\begingroup$ More precisely: If the definition allowed running time $2^{O(n)}$ rather than $O(2^n)$, the class would be exactly alternating time $2^{O(n)}$ with $n$ alternations, starting in an existential state. With the weaker $O(2^n)$ time bound, the class is contained in alternating time $2^{O(n)}$ with $n$ alternations starting in an existential state, and it contains alternating time $2^{O(n)}$ with $n$ alternations starting in an existential state such that the machine is only allowed time $O(2^n)$ before the first alternation. (One can characterize it exactly, but then it gets even more messy.) ... $\endgroup$ – Emil Jeřábek Jun 16 '18 at 16:08

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.