Questions tagged [separation]
Separation of complexity classes in computational complexity theory.
15 questions
4
votes
1
answer
174
views
References for $\mathsf{PSPACE} \neq \mathsf{E}$ and $\mathsf{P} \neq \mathsf{NTIME}(n^k)$
In a recent blog post, Lance Fortnow dropped as a little exercise the task of proving $\mathsf{PSPACE} \neq \mathsf{E}$, using the fact that $\mathsf{EXP}$ is the closure of $\mathsf{E}$ under poly-...
- 2,356
11
votes
1
answer
369
views
How do separations of query complexities imply complexity class separations relative to oracles?
Simon's problem is the following: Given oracle access to a Boolean function $f: \{0,1\}^n\rightarrow \{0,1\}^n$, and promised that precisely one of the following two cases is true, decide which of ...
- 300
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
3
votes
1
answer
323
views
Can we efficiently distinguish between P and BPP?
Let's say algorithm $D$ distinguishes $BPP$ from $P$ if
there exists a language $L \in BPP$ such that for all $A \in PTM$,
$$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A$$...
- 4,495
8
votes
1
answer
157
views
Another planar separator ref question
Do any of you know a reference for the following (surprisingly tedious to prove) result?
Given a connected planar graph $G$ with $n$ vertices and $n+t$ edges, it has a vertex separator of size $O( \...
- 7,049
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
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 ...
- 1,671
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
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
12
votes
3
answers
1k
views
An explicit separation between time-constructibility and space-constructibility?
Show a function $f(n)$ which is space-constructible but not time-constuctible.
Is this problem related to a possible separation between complexity classes DTIME(f(n)) and SPACE(f(n))?
CommunityBot
- 1
6
votes
1
answer
337
views
Decomposition by Clique Separators
Tarjan described a procedure for decomposing a graph using clique separators in "Decomposition by clique separators", RE Tarjan - Discrete mathematics, 1985 - Elsevier.
He also proposed different ...
- 1,583
12
votes
1
answer
491
views
Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$
Complexity Zoology by Greg Kuperberg states that there is a language $X$ such that $\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X$ — in other words, $\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\...
CommunityBot
- 1
10
votes
1
answer
465
views
Could a descriptive complexity version of Rice's theorem be used to separate AC0 and PSPACE?
In this question, it was mentioned that there are descriptive complexity versions of Rice's theorem. I found a proof of the following theorem:
Given a complexity class C, nontrivial properties of ...
CommunityBot
- 1
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 ...
- 21.8k
9
votes
1
answer
226
views
Separation of classes with different amounts of advice?
The time hierarchy theorem lets one show that, for example, there are problems in P that cannot be solved in time less than const*n^2 by a Turing machine. But give the Turing machine some advice and ...
- 21.8k