New answers tagged


Let's define what P$^A$ means in the promise setting: A language L is in P$^A$ if there is a polytime oracle machine $M$ such that for all sets $B$ such that $B$ contains $A_{YES}$ and $B\cap A_{NO}=\emptyset$, $L=L(M^B)$. In other words, the polytime machine can ask queries that are not part of the promise but its output cannot depend on whether those ...

Top 50 recent answers are included