11
votes
Accepted
How do separations in of query complexities imply complexity class separations relative to oracles?
Let $\mathscr{F}$ be the collection of all functions $F:\{0,1\}^*\rightarrow\{0,1\}^*$, such that for every $n$, the restriction $F_n:=F|_{\{0,1\}^n}$ (restriction of $F$ on $\{0,1\}^n$) satisfies the ...
- 723
7
votes
Another planar separator ref question
Here is a proof using a well-known hammer.
Let us assume wlog that $G$ is connected, hence it is a spanning tree plus $t+1$ edges. Clearly any cycle in $G$ must contain one of these $t+1$ edges ...
- 6,979
1
vote
Can we efficiently distinguish between P and BPP?
You defined that 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) \...
- 4,465
Only top scored, non community-wiki answers of a minimum length are eligible