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
    Jul 21 '15 at 22:09
  • 1
    $\begingroup$ Crossposted on cstheory.SE $\endgroup$
    – chazisop
    Jul 22 '15 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$ Jul 22 '15 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
    Jul 24 '15 at 6:27
  • $\begingroup$ @Kaveh, you're right, I mis-read. Thank you! $\endgroup$
    – D.W.
    Jul 24 '15 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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