L/P/PSpace vs P/NP

Question

in 1979 Hopcroft/ Ullman wrote that L ⊆ P ⊆ NP ⊆ PSpace is known but L ⊊ PSpace is the only proper (& trivial) containment known although all are conjectured to be proper containments, and "where things still stand" ~4 decades later.

since then is there any known connection(s) between L ⊊ P, P ⊊ PSpace and P ⊊ NP? are they all still thought to be independent, or are there any sign(s) of some interdependency?

motivation: this question is partly inspired by the recent Backurs-Indyk results tying SETH to O(n²) edit distance. SETH is exponential time and edit distance is PTime. (& also somewhat the question proving lower bounds by proving upper bounds)

Answer 1

The only known proper containment is still $L \subsetneq PSPACE$, though they are all widely believed to be different. All the rest are still wide-open.

The recent work on ``Fine-Grained Complexity", like the Edit Distance result of Backurs and Indyk, side-steps the fact that we can't prove proper containments, like $P\neq NP$. In particular, SETH is a much stronger conjecture than $P \neq NP$, more or less stating that CNF-SAT requires $2^n$ time (not just super-polynomial time). Under this stronger conjecture, if you can show a $2^{n/k}$ reduction from CNF-SAT to problems in $P$ (like Edit Distance), then you get an $\Omega(n^k)$ conditional lower bound based on SETH. So, the distinctions that these works concern themselves with (i.e. $2^{n}$ vs. $2^{(1-\delta)n}$) are much tighter than the distinctions between the traditional complexity classes mentioned in the post.

Similarly, in proving circuit lower bounds by giving faster satisfiability algorithms, we generally only need fine-grained improvements over the trivial $O^\star(2^n)$ algorithms to give lower bounds. For instance, a $2^{n}poly(n^k)/n^{\omega(1)}$ algorithm for CircuitSAT on circuits of $n^k$ gates would prove $NEXP \not \subseteq P/poly$.