2
$\begingroup$

$\Delta_2^P =P^{NP}$, is the set of all languages decidable by a polynomial Turing machine with access to a SAT oracle. I came across a definition of $\Delta_2^P$ as the set of all languages $L$ such that there exists $L_1\in NP, L_2\in coNP$ where $L=L_1\cap L_2$.

I'm trying to prove that a language in $P^{NP}$ can be expressed by such intersection. Let $L$ be some language in $P^{NP}$, $x\in L$ if $M$ (the machine with access to a SAT oracle) accepts $x$ using some transcript $w$ (the answer of the oracle to the queries raised by $M$). I need to make sure $w$ is a valid transcript (i.e. doesn't lie by giving no answers for satisfiable formulas or yes answers for unsatisfiable formulas). I tried somehow encoding this condition in an intersection of a language in $NP$ with a language in $coNP$, but didn't succeed. Can you give a description of $L\in P^{NP}$ using such intersection?

$\endgroup$
4
$\begingroup$

That set is BH2, and BH is a subset of PNP. ​ ​ ​ If ​ BH ⊆ BH2 ​ "then the polynomial hierarchy collapses to" BH3(2), where BH3(2) is the 2nd "level of the Boolean hierarchy over $\Sigma_2^P$."

(So, to answer your question: ​ No, I can't give such a description.)

$\endgroup$
  • $\begingroup$ Thanks! in some hw i saw this definition as $\Delta_2$, and i thought this means the definitions must be equivalent. I blame the schools $\endgroup$ – Ariel Jan 16 '16 at 11:22

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.