# Best $\Pi_k \text{SAT}$ running time?

Define $\Pi_k \text{SAT}$ by 'Given a quantified boolean formula $\varphi = \forall y_1\exists y_2\dots Q_ky_k\mbox{ }\phi(y_1, \dots, y_k)$, where $\phi(y_1, \dots, y_k)$ is boolean predicate with each $y_i$ a vector of variables, $Q_{2j-1} = \forall$ and $Q_{2j} = \exists$ at every $j\in\mathbb N$, is $\varphi$ valid?' (page $99$ in Arora book).

$ETH$ says $\text{SAT}$ and so $\Pi_1\text{SAT}=\overline{\text{SAT}}$ needs $\Omega(2^{c\cdot n_1})$ time at some $c>0$ where $n_1$ is number of variables in $y_1$.

If there are $n=n_1+\dots+n_k$ variables where each $y_i$ has $n_i$ variables then

1. what is the best known algorithm for $\Pi_k \text{SAT}$ at each fixed $k$?

2. Is there a generalized $ETH$ that applies to $\Pi_k\text{SAT}$?

• You didn’t even let me finish my comment, and I won’t bother. But let me add that it is an extremely annoying and abusive behaviour that at any hint of a disagreement, you just delete the whole post so that no one can see it. – Emil Jeřábek Jun 26 '18 at 10:54