<p>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.</p>

<p>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 <em>much</em> 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.</p>

<p>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$.</p>

CC BY-SA 3.0
2015-08-09T09:36:54.263Z
How does this answer the question, which asks about implications (or "interdependencies", whatever that might mean) between three statements?
András Salamon
CC BY-SA 3.0
2015-08-10T01:39:17.063Z
I was aiming to answer the question based on its stated motivation.  I'm not personally aware of any non-trivial "interdependencies" between the statements.
palindrome
CC BY-SA 3.0
2015-08-08T20:58:09.710Z
2015-08-08T20:58:09.710Z
palindrome
<p>in 1979 <a href="https://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation" rel="nofollow noreferrer">Hopcroft/ Ullman</a> wrote that L ⊆ P ⊆ NP ⊆ PSpace is known but L ⊊ PSpace is the only proper (&amp; trivial) containment known although all are conjectured to be proper containments, and "where things still stand" ~4 decades later.</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>motivation: this question is partly inspired by the recent <a href="https://rjlipton.wordpress.com/2015/06/01/puzzling-evidence/" rel="nofollow noreferrer">Backurs-Indyk results</a> tying <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="nofollow noreferrer">SETH</a> to O(n<sup>2</sup>) edit distance. SETH is exponential time and edit distance is PTime. (&amp; also somewhat the question <a href="https://cstheory.stackexchange.com/questions/3229/proving-lower-bounds-by-proving-upper-bounds">proving lower bounds by proving upper bounds</a>)</p>

<cc.complexity-theory><reference-request><lower-bounds><p-vs-np><conditional-results>
L/P/PSpace vs P/NP
vzn
# L/P/PSpace vs P/NP

(Asked by: username_0 on 2015-08-07)

in 1979 [Hopcroft/ Ullman](https://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation) 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](https://rjlipton.wordpress.com/2015/06/01/puzzling-evidence/) tying [SETH](https://en.wikipedia.org/wiki/Exponential_time_hypothesis) 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](https://cstheory.stackexchange.com/questions/3229/proving-lower-bounds-by-proving-upper-bounds))

**Tags:** cc.complexity-theory, reference-request, lower-bounds, p-vs-np, conditional-results

---

## 1 answers

### Answer by username_1 on 2015-08-08. Score: 7 | Accepted answer

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$.

> **Comments:**
> **username_2**: How does this answer the question, which asks about implications (or "interdependencies", whatever that might mean) between three statements?  
> **username_1**: I was aiming to answer the question based on its stated motivation.  I'm not personally aware of any non-trivial "interdependencies" between the statements.  

---

