Questions tagged [separation]

Separation of complexity classes in computational complexity theory.

Filter by
Sorted by
Tagged with
1 vote
0 answers
70 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: ...
Anupam Das's user avatar
7 votes
1 answer
270 views

How do separations in 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 ...
gen's user avatar
  • 260
3 votes
1 answer
318 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$$...
Anonymous's user avatar
  • 4,041
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( \...
Sariel Har-Peled's user avatar
3 votes
0 answers
457 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 "...
user1033363's user avatar
4 votes
0 answers
121 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 ...
Dominik Peters's user avatar
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 ...
Alex Meiburg's user avatar
8 votes
0 answers
152 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. ...
user34681's user avatar
6 votes
1 answer
332 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 ...
Arman's user avatar
  • 934
12 votes
1 answer
490 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}^{\...
Tsuyoshi Ito's user avatar
  • 16.5k
10 votes
1 answer
455 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 ...
user avatar
1 vote
0 answers
283 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 ...
Zirui Wang's user avatar
9 votes
1 answer
211 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 ...
matt hastings's user avatar
11 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))?
Tian Liu's user avatar
  • 521