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.

  • 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 Feb 10 '17 at 13:06

Your Answer

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

Browse other questions tagged or ask your own question.