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(n2) edit distance. SETH is exponential time and edit distance is PTime. (& also somewhat the question proving lower bounds by proving upper bounds)
L/P/PSpace vs P/NP
cc.complexity theory;reference request;lower bounds;p vs np;conditional results
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$.