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?

  • 2
    $\begingroup$ can you describe the notation in words? what is DP? $\endgroup$
    – vzn
    Commented Jul 21, 2015 at 22:09
  • 1
    $\begingroup$ Crossposted on cstheory.SE $\endgroup$
    – chazisop
    Commented Jul 22, 2015 at 9:15
  • $\begingroup$ 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. $\endgroup$ Commented Jul 22, 2015 at 9:41
  • 1
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Commented Jul 24, 2015 at 6:27
  • $\begingroup$ @Kaveh, you're right, I mis-read. Thank you! $\endgroup$
    – D.W.
    Commented Jul 24, 2015 at 16:56

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.