<p>These questions are discussed in detail in the paper</p>

<blockquote>
  <p>Rahul Santhanam, Ryan Williams:<br>
  "Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity"<br>
  Electronic Colloquium on Computational Complexity (ECCC) 2013, #108<br>
  <a href="https://eccc.weizmann.ac.il/report/2013/108/" rel="noreferrer">https://eccc.weizmann.ac.il/report/2013/108/</a></p>
</blockquote>

CC BY-SA 4.0
2018-06-10T15:10:22.237Z
2018-06-10T15:10:22.237Z
Gamow
<p>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).</p>

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

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

<ol>
<li><p>what is the best known algorithm for $\Pi_k \text{SAT}$ at each fixed $k$?</p></li>
<li><p>Is there a generalized $ETH$ that applies to $\Pi_k\text{SAT}$?</p></li>
</ol>

CC BY-SA 4.0
2018-06-26T10:54:23.077Z
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
<cc.complexity-theory><complexity-classes>
Best $\Pi_k \text{SAT}$ running time?
Turbo
# Best $\Pi_k \text{SAT}$ running time?

(Asked by: username_0 on 2018-06-10)

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}$?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2018-06-10. Score: 7

These questions are discussed in detail in the paper

> Rahul Santhanam, Ryan Williams:  
> "Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity"  
> Electronic Colloquium on Computational Complexity (ECCC) 2013, #108  
> <https://eccc.weizmann.ac.il/report/2013/108/>


---

