<p>Building on Michael Wehar's answer, it seems that you can easily show that $NTISP(n^{\log n},poly(n))$ computations can be encoded in polysize such QBFs: you use $O(\log n) $ alternations, each of $poly(n)$ bits, and do an argument similar to Savitch's theorem. Every two alternations will divide the running time of the computation by a $poly(n)$ factor. </p>

<p>I would call the class $\Sigma_{O(\log n)} P$, following the notation in Fortnow's <a href="https://scholar.google.com/scholar?client=ms-android-hms-tmobile-us&amp;um=1&amp;ie=UTF-8&amp;lr&amp;cites=18433057311784608584" rel="nofollow noreferrer">"Time-Space Tradeoffs for Satisfiability" </a> which could also be cited for the argument sketched in the previous paragraph (but please see the paper for earlier references).</p>

CC BY-SA 3.0
2017-02-25T05:35:31.057Z
Thank you very much for the comment and follow-up answer.  I edited my answer and added details on generalizing the argument.  There is actually a time, space, and alternation trade-off for the kinds of computations that can be encoded.
Michael Wehar
CC BY-SA 3.0
2017-02-25T07:39:14.750Z
Thank you for the added reference!  Also, I added a more succinct answer  to hopefully clarify.  Thanks again.  :)
Michael Wehar
CC BY-SA 3.0
2017-02-24T23:21:43.527Z
2017-02-25T06:40:54.103Z
2017-02-25T06:40:54.103Z
Ryan Williams
<p><strong>(1) What we already know:</strong></p>

<p>As you've already stated, QBF with $\log(n)$ alternations of quantifiers is hard for every level of the polynomial hierarchy.</p>

<p><strong>(2) I think that we can also prove the following:</strong></p>

<p>The problem is $NSPACE(log^2(n))$-hard.</p>

<p><strong>(3) Here is my informal justification for the preceding assertion:</strong></p>

<p>Given a $log^2(n)$ space bound NTM and an input string, we need to determine whether there exists an accepting computation on the given input string.</p>

<p>Each configuration in the computation can be represented by essentially $\log^2(n)$ bits.  In other words, we can represent a configuration by a group of $\log^2(n)$ variables.</p>

<p>The idea is that we have a start configuration and a final configuration and we need to guess the computation that happens in between.  We recursively guess the "middle" configurations using exist quantifiers and recurse verifying that the "left" configuration goes to the "middle" and the "middle" configuration goes to the "right" using for all quantifiers.</p>

<p>Now to make this work, instead of picking one "middle" configuration, we need to pick a group of equally spaced "intermediate" configurations between the "left" and "right" configurations.  In particular, we could guess $\sqrt{n}$ equally spaced "intermediate" configurations using exist quantifiers with $\sqrt{n} * log^2(n)$ variables and then recurse on every gap between configurations using for all quantifiers with roughly $\log(n)$ variables.</p>

<p>The recursion only needs to continue on to depth $2 * \log(n)$ to be able to cover a computation of length $\sqrt{n} ^ {2 * \log(n)} = n^{\log(n)} = 2^{\log^2(n)}$ where each configuration has at most $\log^2(n)$ many bits.</p>

<p>Since the recursion is of depth $O(\log(n))$, we only have $O(\log(n))$ groups of variables i.e. alternations.  Since each group of quantifiers only has $\sqrt{n} * log^2(n)$ variables, in total we have $O(\sqrt{n} * log^3(n))$ variables.</p>

<p>Feel free to offer any feedback or corrections.  Thank you very much and I hope this helps a little bit.</p>

<p><strong>(4) A more general assertion as suggested by Ryan's answer:</strong></p>

<p>You should be able to carry out the preceding construction in a more general way.  Consider the following:</p>

<p>At each step of the recursion, break up into $g(n)$ groups of "intermediate" configurations using $c(n)$ bits per configuration.  Then, do the recursion to depth $d(n)$.</p>

<p>As long as we don't have too many variables and too many alternations, this seems to work fine.  Roughly, we need the following to be satisfied:</p>

<ul>
<li>$g(n) * c(n) * d(n) \leq n$</li>
<li>$d(n) \leq \log(n)$</li>
</ul>

<p>Our generalized approach will be used to simulate non-deterministic Turing machines that run for $g(n)^{d(n)}$ steps using $c(n)$ bits of memory.</p>

<p>In particular, we pick the following:</p>

<ul>
<li><p>$g(n) = \sqrt{n}$</p></li>
<li><p>$c(n) = \frac{\sqrt{n}}{2 * log^2{n}}$</p></li>
<li><p>$d(n) = 2 * \log^2(n)$</p></li>
</ul>

<p>The preceding inequalities are satisfied and we can carry out the construction to simulate non-deterministic Turing machines that run for roughly $2^{\log^2(n)}$ steps using $\frac{\sqrt{n}}{2 * log^2{n}}$ bits of memory.</p>

<p>In other words, we have a better hardness result than before.  In particular, the problem is hard for $NTISP(2^{\log^2(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$.</p>

<p><strong>(5) Further generalizations:</strong></p>

<p>In the preceding generalization, we were simulating non-deterministic time and space bounded Turing machines.  However, we may be able to simulate alternating time and space bounded Turing machines as well.</p>

<p>Let me explain a little bit.  So we use roughly $\log(n)$ alternations to do the recursion to depth $\log(n)$.  However, we could use some of the alternations initially, let's say $\sqrt{\log(n)}$.  Then, we could use the remaining $\sqrt{\log(n)}$ alternations to go to depth $\sqrt{\log(n)}$.</p>

<p>In this case, we could simulate alternating Turing machines that have $\sqrt{\log(n)}$ alternations with sublinear witness lengths, run for $2^{\log^{\frac{3}{2}}(n)}$ steps, and use $\frac{\sqrt{n}}{2 * log^2{n}}$ bits of memory.</p>

<p>In other words, the problem is hard for $AltTimeSpace(\sqrt{\log(n)}, 2^{\log^{\frac{3}{2}}(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$ with sublinear witness lengths.  Alternatively, this class could be written using the $STA$ notation mentioned in the comments above.</p>

<p>Thank you for the comments and feel free to offer any further corrections or clarifications.  :)</p>

CC BY-SA 3.0
2017-02-24T11:41:58.157Z
Wouldn't the $NL^2$-hardness follow straightaway from PH-hardness?
Nikhil
CC BY-SA 3.0
2017-02-24T15:16:35.737Z
@Nikhil I think not because $PH$ vs $L$ is still an open problem.  In other words, we still haven't shown that $L \subsetneq PH$.  Even worse than this, I'm not even sure if we've been able to show that $L \subsetneq P^{PP}$.
Michael Wehar
CC BY-SA 3.0
2017-02-24T15:18:09.490Z
However, in the case of this problem.  We do know that we cannot solve it in logspace.
Michael Wehar
CC BY-SA 3.0
2017-02-24T15:22:32.027Z
Thank you for the question and feel free to ask more or feel free to provide any corrections to what I've said.  :)
Michael Wehar
CC BY-SA 3.0
2017-02-24T20:03:37.207Z
How exactly do we know point (1)? Don't we need $2^k$ variables to get to some level $k$ of PH? Maybe I'm missing a simple point here.
Markus
CC BY-SA 3.0
2017-02-24T21:01:09.487Z
@MichaelWehar Sure, but we do know that $NL^2 \subseteq PH$ right? And that means every problem in $NL^2$ reduces to QBF with constantly many alternations, which is a special case of log-many alternations?
Nikhil
CC BY-SA 3.0
2017-02-24T21:17:24.300Z
@MichaelWehar Oops. Of course you're right! A related question here: http://cstheory.stackexchange.com/questions/14159/what-are-the-consequences-of-mathsfl2-subseteq-mathsfp/32944#32944
Nikhil
CC BY-SA 3.0
2017-02-24T23:22:50.553Z
Why not $NTISP(n^{\log n},poly(n))$-hard?
Ryan Williams
CC BY-SA 3.0
2017-02-25T04:46:04.787Z
@RyanWilliams Thank you Ryan!!  Added a section on generalizing the argument based on your comment and answer.  :)
Michael Wehar
CC BY-SA 3.0
2017-02-25T05:33:03.407Z
@Markus Thank you for the comment!  So basically, if we consider the QBF problem with exactly $k$ alternations for some fixed $k$, then we can efficiently reduce this problem to QBF with $\log(n)$ alternations.  Basically, as long as we have at least $2^k$ variables, then the instance is trivially reduced.  Otherwise, if we have fewer than $2^k$ variables, then we just solve it in essentially $2^k$ times the input size which is polynomial because $k$ is fixed.  Does this help a little bit?
Michael Wehar
CC BY-SA 3.0
2017-02-26T07:13:16.283Z
@MichaelWehar Thanks for the answer. I didn't see that we can fix $k$ in the reduction.
Markus
CC BY-SA 3.0
2017-02-26T08:11:05.167Z
@Markus No problem at all.  Please feel free to ask any further question.  Hope all is well.  :)
Michael Wehar
CC BY-SA 3.0
2017-02-24T05:58:30.933Z
2017-02-25T10:07:37.650Z
2017-02-25T10:07:37.650Z
Michael Wehar
<p><strong>A shorter answer.</strong></p>

<blockquote>
  <p><strong>Initial observations:</strong></p>
  
  <ul>
  <li>The problem is hard for every level of the polynomial hierarchy.</li>
  <li>The problem is hard for alternating Turing machines with $\log(n)$ alternations that run for polynomial time.</li>
  </ul>
  
  <p><strong>Deeper Insights:</strong></p>
  
  <ul>
  <li>Suggested by Kaveh's comment above, the problem can encode computations for $AltTime(\log(n), n)$ Turing machines.</li>
  <li>Also, as Ryan pointed out, the problem can encode computations for $NTimeSpace(2^{\log^2(n)}, \sqrt{n})$ Turing machines.</li>
  <li><p>More generally, the problem can encode computations for machines corresponding to various classes of the form $AltTimeSpace(a(n), t(n), s(n))$ with restricted witness lengths.  I'm not quite sure what the exact relationship between
  $a(n)$, $t(n)$, and $s(n)$ has to be, but we know that:</p>
  
  <ol>
  <li><p>$\; \; a(n) \leq \log(n)$</p></li>
  <li><p>$\; \; t(n) \leq 2^{\log^2(n)}$</p></li>
  <li><p>$\; \; s(n) \leq n$</p></li>
  </ol></li>
  </ul>
</blockquote>

<p>See my longer answer for more details on the trade-offs between $a(n)$, $t(n)$, and $s(n)$.</p>

<p><strong>Note:</strong> In the above, when I say encode computations, I mean encode the computation without blowing up the instance size too much.  That is, if we blow-up from $n$ size Turing machine input to $poly(n)$ size formula, then I think that although the blow-up is polynomial, it is good to pay close attention to the degree of the polynomial.  The reason for the semi-fine-grained perspective is to try and slightly better recognize how the different complexity measures $a(n)$, $t(n)$, and $s(n)$ depend on each other.</p>

CC BY-SA 3.0
2017-02-25T06:33:11.863Z
Also, there is another factor that I omitted.  That is, the witness size used with each alternation takes up variables.  In other words, the larger the witnesses, the fewer variables that we have meaning that potentially we can't represent as many bits per configuration causing us to possibly require there to be less space for the machine that we encode computations for.
Michael Wehar
CC BY-SA 3.0
2017-02-25T10:12:33.487Z
Basically, all witness lengths for the quantifiers are sublinear and how large we can make them depends on the choice of $a(n)$, $t(n)$, and $s(n)$.
Michael Wehar
CC BY-SA 3.0
2017-02-25T17:10:54.787Z
Maybe an inner most there exists quantifier doesn't need to have restricted witness size because we can guess as we go.
Michael Wehar
CC BY-SA 3.0
2017-02-25T06:06:15.167Z
2017-02-25T10:06:32.110Z
2017-02-25T10:06:32.110Z
Michael Wehar
<p>I'm studying a problem which is hard for the class of quantified boolean formulas with a logarithmic number of alternations of the quantifiers. A problem in this class would look like:</p>

<p>$\forall (x_1, x_2, \ldots x_{a_1}) \exists (x_{{a_1}+1}, \ldots x_{a_2}), \ldots \exists(x_{a_{\log n - 1}}, \ldots x_{a_{\log n}})F$</p>

<p>Where $a_{\log n} = n$, and $F$ is a boolean formula of the variables $x_1 \ldots x_n$.</p>

<p>This class clearly contains $PH$ and is contained in $AP = PSPACE$. Is there a name for this class? Is there anything more known about it?</p>

CC BY-SA 3.0
2017-02-24T09:07:10.760Z
Well, it's complete for alternating polynomial time with logarithmically many alternations.
Emil Jeřábek
CC BY-SA 3.0
2017-02-24T12:18:43.300Z
An agreed notation for the complexity class of this problem would be STA($\ast,n^{O(1)}, O(\log n)$). Here, STA(s(n), t(n), a(n)) is the space-time-alternation measure introduced by Berman in "The complexity of logical theories" which appeared in TCS in 1980. This class contains all decision problem decidable by an alternating Turing machine in time t(n) using space s(n) and alternating at most a(n) times on every computation branch. As Emil pointed out, your problem should be complete for this class.
Christoph Haase
CC BY-SA 3.0
2017-02-25T03:06:28.357Z
AltTime(lg n, poly(n))
Kaveh
CC BY-SA 3.0
2017-02-27T15:24:03.447Z
Isn't it also the binary analog of the class FOLL introduced by Barrington, Kadau, McKenzie and Lange. FOLL is defined by iterating an FO block basically an n-input, n-output uniform AC0 circuit loglog n times. It is too weak to compute Parity but is not known to be contained in a class smaller than AC^1. It can do a number of nontrivial stuff including powering in a commutative group presented as a multiplication table. I would like to call the class in question PHL because it corresponds to a PH block iterated log n times. I think it is still not clear if it is comparable to PSPACE.
SamiD
CC BY-SA 3.0
2017-02-27T15:28:19.797Z
Also if an abelian group is given by a circuit which takes input two n-bit numbers and outputs an n-bit number then powering is in PHL by a proof similar to Barrington et al above.
SamiD
CC BY-SA 3.0
2017-02-27T15:31:28.443Z
please ignore comment about comparability with PSPACE. of course it is contained in PSPACE.
SamiD
<cc.complexity-theory><boolean-formulas>
Quantified Boolean Formulas with logarithmic alternations
isaacg
# Quantified Boolean Formulas with logarithmic alternations

(Asked by: username_0 on 2017-02-23)

I'm studying a problem which is hard for the class of quantified boolean formulas with a logarithmic number of alternations of the quantifiers. A problem in this class would look like:

$\forall (x\_1, x\_2, \ldots x\_{a\_1}) \exists (x\_{{a\_1}+1}, \ldots x\_{a\_2}), \ldots \exists(x\_{a\_{\log n - 1}}, \ldots x\_{a\_{\log n}})F$

Where $a\_{\log n} = n$, and $F$ is a boolean formula of the variables $x\_1 \ldots x\_n$.

This class clearly contains $PH$ and is contained in $AP = PSPACE$. Is there a name for this class? Is there anything more known about it?

**Tags:** cc.complexity-theory, boolean-formulas
> **Comments:**
> **username_1**: Well, it's complete for alternating polynomial time with logarithmically many alternations.  
> **username_2**: An agreed notation for the complexity class of this problem would be STA($\ast,n^{O(1)}, O(\log n)$). Here, STA(s(n), t(n), a(n)) is the space-time-alternation measure introduced by Berman in "The complexity of logical theories" which appeared in TCS in 1980. This class contains all decision problem decidable by an alternating Turing machine in time t(n) using space s(n) and alternating at most a(n) times on every computation branch. As Emil pointed out, your problem should be complete for this class.  
> **username_3**: AltTime(lg n, poly(n))  
> **username_4**: Isn't it also the binary analog of the class FOLL introduced by Barrington, Kadau, McKenzie and Lange. FOLL is defined by iterating an FO block basically an n-input, n-output uniform AC0 circuit loglog n times. It is too weak to compute Parity but is not known to be contained in a class smaller than AC^1. It can do a number of nontrivial stuff including powering in a commutative group presented as a multiplication table. I would like to call the class in question PHL because it corresponds to a PH block iterated log n times. I think it is still not clear if it is comparable to PSPACE.  
> **username_4**: Also if an abelian group is given by a circuit which takes input two n-bit numbers and outputs an n-bit number then powering is in PHL by a proof similar to Barrington et al above.  
> **username_4**: please ignore comment about comparability with PSPACE. of course it is contained in PSPACE.  

---

## 3 answers

### Answer by username_5 on 2017-02-24. Score: 8

Building on Michael Wehar's answer, it seems that you can easily show that $NTISP(n^{\log n},poly(n))$ computations can be encoded in polysize such QBFs: you use $O(\log n) $ alternations, each of $poly(n)$ bits, and do an argument similar to Savitch's theorem. Every two alternations will divide the running time of the computation by a $poly(n)$ factor.

I would call the class $\Sigma\_{O(\log n)} P$, following the notation in Fortnow's ["Time-Space Tradeoffs for Satisfiability"](https://scholar.google.com/scholar?client=ms-android-hms-tmobile-us&um=1&ie=UTF-8&lr&cites=18433057311784608584)  which could also be cited for the argument sketched in the previous paragraph (but please see the paper for earlier references).

> **Comments:**
> **username_6**: Thank you very much for the comment and follow-up answer.  I edited my answer and added details on generalizing the argument.  There is actually a time, space, and alternation trade-off for the kinds of computations that can be encoded.  
> **username_6**: Thank you for the added reference!  Also, I added a more succinct answer  to hopefully clarify.  Thanks again.  :)  

---

### Answer by username_6 on 2017-02-24. Score: 8

**(1) What we already know:**

As you've already stated, QBF with $\log(n)$ alternations of quantifiers is hard for every level of the polynomial hierarchy.

**(2) I think that we can also prove the following:**

The problem is $NSPACE(log^2(n))$-hard.

**(3) Here is my informal justification for the preceding assertion:**

Given a $log^2(n)$ space bound NTM and an input string, we need to determine whether there exists an accepting computation on the given input string.

Each configuration in the computation can be represented by essentially $\log^2(n)$ bits. In other words, we can represent a configuration by a group of $\log^2(n)$ variables.

The idea is that we have a start configuration and a final configuration and we need to guess the computation that happens in between. We recursively guess the "middle" configurations using exist quantifiers and recurse verifying that the "left" configuration goes to the "middle" and the "middle" configuration goes to the "right" using for all quantifiers.

Now to make this work, instead of picking one "middle" configuration, we need to pick a group of equally spaced "intermediate" configurations between the "left" and "right" configurations. In particular, we could guess $\sqrt{n}$ equally spaced "intermediate" configurations using exist quantifiers with $\sqrt{n} \* log^2(n)$ variables and then recurse on every gap between configurations using for all quantifiers with roughly $\log(n)$ variables.

The recursion only needs to continue on to depth $2 \* \log(n)$ to be able to cover a computation of length $\sqrt{n} ^ {2 \* \log(n)} = n^{\log(n)} = 2^{\log^2(n)}$ where each configuration has at most $\log^2(n)$ many bits.

Since the recursion is of depth $O(\log(n))$, we only have $O(\log(n))$ groups of variables i.e. alternations. Since each group of quantifiers only has $\sqrt{n} \* log^2(n)$ variables, in total we have $O(\sqrt{n} \* log^3(n))$ variables.

Feel free to offer any feedback or corrections. Thank you very much and I hope this helps a little bit.

**(4) A more general assertion as suggested by Ryan's answer:**

You should be able to carry out the preceding construction in a more general way. Consider the following:

At each step of the recursion, break up into $g(n)$ groups of "intermediate" configurations using $c(n)$ bits per configuration. Then, do the recursion to depth $d(n)$.

As long as we don't have too many variables and too many alternations, this seems to work fine. Roughly, we need the following to be satisfied:

* $g(n) \* c(n) \* d(n) \leq n$
* $d(n) \leq \log(n)$

Our generalized approach will be used to simulate non-deterministic Turing machines that run for $g(n)^{d(n)}$ steps using $c(n)$ bits of memory.

In particular, we pick the following:

* $g(n) = \sqrt{n}$
* $c(n) = \frac{\sqrt{n}}{2 \* log^2{n}}$
* $d(n) = 2 \* \log^2(n)$

The preceding inequalities are satisfied and we can carry out the construction to simulate non-deterministic Turing machines that run for roughly $2^{\log^2(n)}$ steps using $\frac{\sqrt{n}}{2 \* log^2{n}}$ bits of memory.

In other words, we have a better hardness result than before. In particular, the problem is hard for $NTISP(2^{\log^2(n)}, \frac{\sqrt{n}}{2 \* log^2{n}})$.

**(5) Further generalizations:**

In the preceding generalization, we were simulating non-deterministic time and space bounded Turing machines. However, we may be able to simulate alternating time and space bounded Turing machines as well.

Let me explain a little bit. So we use roughly $\log(n)$ alternations to do the recursion to depth $\log(n)$. However, we could use some of the alternations initially, let's say $\sqrt{\log(n)}$. Then, we could use the remaining $\sqrt{\log(n)}$ alternations to go to depth $\sqrt{\log(n)}$.

In this case, we could simulate alternating Turing machines that have $\sqrt{\log(n)}$ alternations with sublinear witness lengths, run for $2^{\log^{\frac{3}{2}}(n)}$ steps, and use $\frac{\sqrt{n}}{2 \* log^2{n}}$ bits of memory.

In other words, the problem is hard for $AltTimeSpace(\sqrt{\log(n)}, 2^{\log^{\frac{3}{2}}(n)}, \frac{\sqrt{n}}{2 \* log^2{n}})$ with sublinear witness lengths. Alternatively, this class could be written using the $STA$ notation mentioned in the comments above.

Thank you for the comments and feel free to offer any further corrections or clarifications. :)

> **Comments:**
> **username_7**: Wouldn't the $NL^2$-hardness follow straightaway from PH-hardness?  
> **username_6**: @Nikhil I think not because $PH$ vs $L$ is still an open problem.  In other words, we still haven't shown that $L \subsetneq PH$.  Even worse than this, I'm not even sure if we've been able to show that $L \subsetneq P^{PP}$.  
> **username_6**: However, in the case of this problem.  We do know that we cannot solve it in logspace.  
> **username_6**: Thank you for the question and feel free to ask more or feel free to provide any corrections to what I've said.  :)  
> **username_8**: How exactly do we know point (1)? Don't we need $2^k$ variables to get to some level $k$ of PH? Maybe I'm missing a simple point here.  
> **username_7**: @MichaelWehar Sure, but we do know that $NL^2 \subseteq PH$ right? And that means every problem in $NL^2$ reduces to QBF with constantly many alternations, which is a special case of log-many alternations?  
> **username_7**: @MichaelWehar Oops. Of course you're right! A related question here: http://cstheory.stackexchange.com/questions/14159/what-are-the-consequences-of-mathsfl2-subseteq-mathsfp/32944#32944  
> **username_5**: Why not $NTISP(n^{\log n},poly(n))$-hard?  
> **username_6**: @RyanWilliams Thank you Ryan!!  Added a section on generalizing the argument based on your comment and answer.  :)  
> **username_6**: @Markus Thank you for the comment!  So basically, if we consider the QBF problem with exactly $k$ alternations for some fixed $k$, then we can efficiently reduce this problem to QBF with $\log(n)$ alternations.  Basically, as long as we have at least $2^k$ variables, then the instance is trivially reduced.  Otherwise, if we have fewer than $2^k$ variables, then we just solve it in essentially $2^k$ times the input size which is polynomial because $k$ is fixed.  Does this help a little bit?  
> **username_8**: @MichaelWehar Thanks for the answer. I didn't see that we can fix $k$ in the reduction.  
> **username_6**: @Markus No problem at all.  Please feel free to ask any further question.  Hope all is well.  :)  

---

### Answer by username_6 on 2017-02-25. Score: 1

**A shorter answer.**

> **Initial observations:**
>
> * The problem is hard for every level of the polynomial hierarchy.
> * The problem is hard for alternating Turing machines with $\log(n)$ alternations that run for polynomial time.
>
> **Deeper Insights:**
>
> * Suggested by Kaveh's comment above, the problem can encode computations for $AltTime(\log(n), n)$ Turing machines.
> * Also, as Ryan pointed out, the problem can encode computations for $NTimeSpace(2^{\log^2(n)}, \sqrt{n})$ Turing machines.
> * More generally, the problem can encode computations for machines corresponding to various classes of the form $AltTimeSpace(a(n), t(n), s(n))$ with restricted witness lengths. I'm not quite sure what the exact relationship between
>   $a(n)$, $t(n)$, and $s(n)$ has to be, but we know that:
>
>   1. $\; \; a(n) \leq \log(n)$
>   2. $\; \; t(n) \leq 2^{\log^2(n)}$
>   3. $\; \; s(n) \leq n$

See my longer answer for more details on the trade-offs between $a(n)$, $t(n)$, and $s(n)$.

**Note:** In the above, when I say encode computations, I mean encode the computation without blowing up the instance size too much. That is, if we blow-up from $n$ size Turing machine input to $poly(n)$ size formula, then I think that although the blow-up is polynomial, it is good to pay close attention to the degree of the polynomial. The reason for the semi-fine-grained perspective is to try and slightly better recognize how the different complexity measures $a(n)$, $t(n)$, and $s(n)$ depend on each other.

> **Comments:**
> **username_6**: Also, there is another factor that I omitted.  That is, the witness size used with each alternation takes up variables.  In other words, the larger the witnesses, the fewer variables that we have meaning that potentially we can't represent as many bits per configuration causing us to possibly require there to be less space for the machine that we encode computations for.  
> **username_6**: Basically, all witness lengths for the quantifiers are sublinear and how large we can make them depends on the choice of $a(n)$, $t(n)$, and $s(n)$.  
> **username_6**: Maybe an inner most there exists quantifier doesn't need to have restricted witness size because we can guess as we go.  

---

