6
$\begingroup$

I am looking for the name and a reference for a $\Delta_2^P$-complete problem that looks like the following

Input: A collection of CNF formulas $\phi_i(x_1^i, x_2^i,\dots, x_m^i, z_1, z_2, \dots, z_{i-1})$ for $1 \leq i \leq n$ where the $x_j^i$ are free variables and the $z_i$ variables are bound, and the value of $z_i$ is true if $\phi_i$ is satisfiable and false if $\phi_i$ is unsatisfiable.
Output: Whether $\phi_n$ is satisfiable.

I looked at https://cs.stackexchange.com/questions/14251/which-problems-are-hard-for-pnp and at https://mathoverflow.net/questions/2218/characterize-pnp-a-k-a-delta-2p but couldn't find what I'm looking for. I believe I came across a paper mentioning a problem defined similarly to the one above a couple months ago, but I don't remember which paper was listing it. I am not 100% sure about my recollection of the problem definition and this is one of the reasons behind this reference request.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ I don’t know a reference, but yes, this problem is $\Delta^P_2$-complete, which is reasonably obvious from the proof of the Cook–Levin theorem. $\endgroup$
    – Emil Jeřábek
    Commented Feb 10, 2017 at 13:06

0

Reset to default

Your Answer

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