Questions tagged [separation]
Separation of complexity classes in computational complexity theory.
6 questions with no upvoted or accepted answers
8
votes
0
answers
153
views
Manuel's trick and oracle separation
Impagliazzo gave a talk last week at Simons Institute on oracle separation. At minute 5:34 he asks whether a one-way permutation can be constructed given oracle access to a random function oracle. ...
- 81
4
votes
0
answers
123
views
When is $FP^{NP[f(n)]}$ the same as $FP^{NP}$?
I am very confused, so this might not make sense. I am following the exposition in the polynomial hierarchy chapter of Papadimitriou's textbook.
We are in the function-problem world. The problem ...
- 391
4
votes
0
answers
98
views
Are there any non-relativized separations between $L$ and $PH$?
In one sense, $P$ vs. $PSPACE$ is the "easiest" first step to showing $P \neq NP$... and this is one you hear often about. In a different sense, you could take $L$ at one end and then $PH$ at the ...
- 856
3
votes
0
answers
482
views
Oracle separating $coNP$ and $NP/poly$
I'd like to prove that, with respect to some adversarial oracle $O$, $coNP^O \not\subseteq NP/poly^O$. I was thinking of using $\textsf{UNSAT}$ for this and to build my oracle as follows: $O$ will "...
- 137
1
vote
0
answers
83
views
Separating disjoint PSPACE-hard sets by NP-separators (and some variants)
I am trying to find some references or arguments for results of the form, where $X,Y$ vary over complexity classes, typically with $X\subseteq Y$, and $A,B$ are disjoint languages that are $Y$-hard:
...
- 171
1
vote
0
answers
294
views
Separating the QIP hierarchy
Background: I'm a CS grad student. I've taken a course on computational complexity.
Question:
Can you suggest an introductory book on quantum computation, especially regarding the details of ...
- 551