# Complexity of a SAT related problem

Given a set of (propositional) formulae $\Phi$, two formulae $\phi$ and $\xi$, determine whether there exists $\Psi\subseteq \Phi$ such that $\Psi\models \phi$ and $\Psi\not\models \xi$.

Question: what is the (theoretical) complexity of this problem? Is it in DP?

• can you describe the notation in words? what is DP?
– vzn
Commented Jul 21, 2015 at 22:09
• Crossposted on cstheory.SE Commented Jul 22, 2015 at 9:15
• I found the definition of DP: cse.buffalo.edu/~regan/papers/pdf/ALRch29.pdf and search for "is the class of languages A". DP is the class of languages A such that A = A1 ∩ A2 for some languages A1 in NP and A2 in co-NP. Commented Jul 22, 2015 at 9:41
• @D.W., they are sets so is there a reason not to read it simply as "subset"? Also you can find the definition of DP on complexity zoo. Commented Jul 24, 2015 at 6:27
• @Kaveh, you're right, I mis-read. Thank you!
– D.W.
Commented Jul 24, 2015 at 16:56

Given a propositional formula $\varphi(\vec{x}, \vec{y})$, consider $\psi = \exists \vec{y} \ \forall \vec{x} \ \varphi(\vec{x}, \vec{y})$.
Let $\Delta = \{ y_0 \leftrightarrow \top, y_0 \leftrightarrow \bot, \ldots, y_m \leftrightarrow \top, y_m \leftrightarrow \bot \}$. Then $\psi$ is true iff there exists $\Gamma \subseteq \Delta$ such that $\Gamma \nvDash \bot$ and $\Gamma \vDash \varphi(\vec{x}, \vec{y})$.
Therefore the problem is $\Sigma^\mathsf{P}_2$-hard. $\mathsf{DP} \subseteq \Delta^\mathsf{P}_2$, so unless $\mathsf{PH}$ collapses the problem is not in $\mathsf{DP}$.