World's most popular travel blog for travel bloggers.

[Solved]: Different characterization of $\Delta_2^P$

, , No Comments
Problem Detail: 

$\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?

Asked By : Ariel

Answered By : Ricky Demer

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.)

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback