<p>Given a sequence of $n$ propositional formulas $\varphi_1, \cdots, \varphi_n$, a propositional formula $\phi$, a number $1\leq \theta\leq n$.</p>

<p>Define $K=\min\{k\mid \wedge_{i=k}^n \varphi_i\not\models \phi\}$, i.e., it is the minimal number $k$ such that the conjunction of $\varphi_k, \cdots, \varphi_n$ does <em>not</em> imply $\phi$.</p>

<p>Question: what's the complexity of deciding whether $K=\theta$?</p>

<p>What I have tried: Since deciding $\wedge_{i=k}^n\varphi_i\not\models \phi$ is NP-complete, this problem is in $P^{NP}$. Moreover, by binary search, this can be improved to $\Theta^p_2$, i.e., only logarithmic number of NP queries is enough. (Is this correct?) However, I am not clear about the lower bound. Maybe it is just in NP?</p>

CC BY-SA 3.0
2015-07-17T12:01:42.973Z
You only need to test $\theta$ and $\theta+1$, so the problem is in DP. It’s not difficult to prove that it’s actually DP-complete.
Emil Jeřábek
CC BY-SA 3.0
2015-07-17T12:15:49.667Z
I mean $\theta$ and $\theta-1$.
Emil Jeřábek
CC BY-SA 3.0
2015-07-17T13:28:48.037Z
Thanks. I am not familiar with DP, so could you please outline the DP-hardness?
maomao
CC BY-SA 3.0
2015-07-18T14:16:52.933Z
@NieldeBeaudrap Note that the intersection is pointwise. And you probably mean $\mathsf{BH}_2$.
Cornelius Brand
<cc.complexity-theory><sat><polynomial-hierarchy>
A SAT related question
maomao
# A SAT related question

(Asked by: username_0 on 2015-07-17)

Given a sequence of $n$ propositional formulas $\varphi\_1, \cdots, \varphi\_n$, a propositional formula $\phi$, a number $1\leq \theta\leq n$.

Define $K=\min\{k\mid \wedge\_{i=k}^n \varphi\_i\not\models \phi\}$, i.e., it is the minimal number $k$ such that the conjunction of $\varphi\_k, \cdots, \varphi\_n$ does *not* imply $\phi$.

Question: what's the complexity of deciding whether $K=\theta$?

What I have tried: Since deciding $\wedge\_{i=k}^n\varphi\_i\not\models \phi$ is NP-complete, this problem is in $P^{NP}$. Moreover, by binary search, this can be improved to $\Theta^p\_2$, i.e., only logarithmic number of NP queries is enough. (Is this correct?) However, I am not clear about the lower bound. Maybe it is just in NP?

**Tags:** cc.complexity-theory, sat, polynomial-hierarchy

> **Comments:**
> **username_1**: You only need to test $\theta$ and $\theta+1$, so the problem is in DP. It’s not difficult to prove that it’s actually DP-complete.  
> **username_1**: I mean $\theta$ and $\theta-1$.  
> **username_0**: Thanks. I am not familiar with DP, so could you please outline the DP-hardness?  
> **username_2**: @NieldeBeaudrap Note that the intersection is pointwise. And you probably mean $\mathsf{BH}_2$.  

---

## 0 answers

