All Questions
Tagged with structural-complexity cc.complexity-theory
3 questions with no upvoted or accepted answers
22
votes
0
answers
800
views
What is the power of general poly-size permutation branching programs?
Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions ...
- 5,628
9
votes
0
answers
270
views
Is the infinitely-often version of Ladner's theorem known?
We say two languages $\;\;\; L\hspace{.02 in},\hspace{-0.02 in}L' \: \subseteq \: \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^* \;\;\;$ agree infinitely-often with each other
if and ...
user6973
1
vote
0
answers
101
views
Is complexity class containment preserved relative to any oracle?
That is, suppose $A\subseteq B$ for two complexity classes $A$ and $B$. Is it the case that for any oracle $C$, and any definitions $A^*$ and $B^*$ of $A$ and $B$, we have ${A^*}^C\subseteq {B^*}^C$? (...
