All Questions
Tagged with separation reference-request
2 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-...
- 1,049
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( \...
- 9,636