<p>I'd love to be shown wrong, but I don't think there are currently any uniform lower bounds that aren't ultimately based on one of the hierarchy theorems. Our current understanding of how to take advantage of uniformity is really quite limited in that sense.</p>

<p>On the other hand, there are many uniform lower bounds that don't follow <em>directly</em> from hierarchy theorems, but use a hierarchy theorem in combination with other clever tricks, techniques, and results, for example: </p>

<ul>
<li>$\mathsf{CSL} \not\subseteq \mathsf{DTIME}(n)$ [<a href="http://dx.doi.org/10.1145/322003.322015">Hopcroft-Paul-Valiant</a>]. They prove that $\mathsf{DTIME}(n) \subseteq \mathsf{DSPACE}(n/\log n)$ (the non-diagonalization part of their proof), and then use the fact that $\mathsf{CSL} = \mathsf{NSPACE}(n)$ in combination with the space hierarchy. Their result + the space hierarchy also implies $\mathsf{DSPACE}(n) \nsubseteq \mathsf{DTIME}(n)$.</li>
<li>Time-space trade-offs for Satisfiability (see, e.g. the introductions of <a href="http://eccc.hpi-web.de/report/2011/031/">Buss-Williams</a> and references therein)</li>
<li>$\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$ [<a href="http://dx.doi.org/10.1109/SFCS.1983.39">Paul-Pippinger-Szemeredi-Trotter</a>]. Uses a nontrivial simulation of any deterministic super-linear-time machine by a faster four-alternation machine, in combination with the deterministic time hierarchy.</li>
<li>Uniform lower bounds on the permanant [<a href="http://dx.doi.org/10.4086/cjtcs.1999.007">Allender</a>, <a href="http://dx.doi.org/10.1137/S0097539792233907">Allender-Gore</a>, <a href="http://dx.doi.org/10.1109/CCC.2009.19">Koiran-Perifel</a>]</li>
<li>$\mathsf{NEXP} \not\subseteq \mathsf{ACC}^0$ [<a href="http://dx.doi.org/10.1145/2559903">Williams</a>] (although technically this is a nonuniform lower bound, it uses a bunch of clever ideas in combination with the nondeterministic time hierarchy)</li>
</ul>

CC BY-SA 3.0
2014-02-25T01:41:54.813Z
2014-02-25T01:41:54.813Z
Joshua Grochow
<p>Is the separation $\mathsf{AC}^0\subsetneq\mathsf{TC}^0$ by <a href="http://dx.doi.org/10.1145/28395.28404" rel="nofollow">Smolensky</a> something you have been looking for?</p>

CC BY-SA 3.0
2014-02-25T13:23:19.303Z
Thank you, that is a nice result, but I am looking for separations of $uniform$ classes, not circuit classes.
Andras Farago
CC BY-SA 3.0
2014-02-25T20:08:50.160Z
@AndresFarago: Uniform AC^0 is also properly included in uniform TC^0.
Emil Jeřábek
CC BY-SA 3.0
2014-02-25T21:45:09.903Z
@EmilJeřábek: Is there a proof that uniform $\mathsf{AC}^0$ is properly contained in uniform $\mathsf{TC}^0$ that doesn't also already prove the nonuniform statement? (If not, then it would seem your example falls under the general principle that nonuniform lower bounds are stronger than uniform lower bounds, and I think the OQ was trying to avoid such answers...)
Joshua Grochow
CC BY-SA 3.0
2014-02-27T23:26:41.067Z
I think the nonuniformity in the proofs is secondary to the fact that these are rather small classes where we have some nice combinatorial/algebraic understanding of them. I.e. we understand them well enough to directly construct an object which is not in them. Where are for larger classes there is no such understanding and therefore the only method we know is to do diagonalization against the whole class to construct such objects.
Kaveh
CC BY-SA 3.0
2014-02-25T08:22:48.900Z
2014-02-25T08:22:48.900Z
Arne
<p>Another nontrivial example comes from the area of average case complexity. Rainer Schuler proves interesting properties of the class he calls $P_{P-comp}$, see [1]. </p>

<p>$P_{P-comp}$ is the class of languages that are accepted in polynomial time on $\mu$-average for <em>every</em> polynomial time  computable (P-computable) distribution $\mu$. Naturally, $P\subseteq P_{P-comp}$ holds, since the existence of a deterministic polytime algorithm implies that it remains efficient on the average, no matter the what the input distribution is.  However, the condition of running in average polynomial time for <strong>every</strong> P-computable input distribution appears strong enough to suspect  $P_{P-comp}=P$.</p>

<p>Surprisingly, Schuler proves that there is a language  $L\in P_{P-comp}$, which is Turing-complete for $E$, that is,
$$E\subseteq P^{P_{P-comp}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; (*)$$
This implies the unconditional separation $P_{P-comp}\neq P$. While the latter also uses the fact $E\neq P$, which follows from the Time Hierarchy Theorem, the novel part (*) builds on different tools: beyond diagonalization, it employs resource bounded measure and  Kolmogorov complexity.</p>

<p>Reference:</p>

<p>[1] R. Schuler, "Truth-table closure and Turing closure of average polynomial time have different measures in EXP," CCC 1996, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.1686&amp;rep=rep1&amp;type=pdf" rel="nofollow">pdf</a></p>

CC BY-SA 4.0
2021-01-03T17:43:54.537Z
Do not understand. In abstract he says '$\dots$ $P_{P-comp}$ is an example of
a subclass of $E\dots$' and so it appears $P_{P-comp}\subseteq E\subseteq P^{P_{P-comp}}$. Is $PSPACE\subseteq P_{P-comp}$?
Turbo
CC BY-SA 3.0
2014-02-27T23:04:57.363Z
2014-02-27T23:04:57.363Z
Andras Farago
<p>Hierarchy theorems are fundamental tools. A good number of them was collected in an earlier question (see <a href="https://cstheory.stackexchange.com/questions/7303/what-hierarchies-and-or-hierarchy-theorems-do-you-know">What hierarchies and/or hierarchy theorems do you know?</a>). Some complexity class separations directly follow from hierarchy theorems.  Examples of such well known separations: $L\neq PSPACE$, $P\neq EXP$, $NP\neq NEXP$, $PSPACE\neq EXPSPACE$. </p>

<p>However, not every separation follows from a hierarchy theorem. A very simple example is $NP\neq E$. Even though we do not know if any of them contains the other, they are still different, because $NP$ is closed with respect to polynomial transformations, while $E$ is not. </p>

<p>Which are some deeper, unconditional, non-relativized complexity class separations for uniform classes that  do <strong>not</strong> directly follow from some hierarchy theorem? </p>

CC BY-SA 3.0
2014-02-22T05:44:38.333Z
I think it is a bit unusual to call $NP\neq E$ a separation. Also their inequality is for trivial reasons and doesn't tell us anything interesting. AFAIK all interesting complexity class separations for large complexity classes rely on hierarchy theorems (and in turn diagonalization) at some point.
Kaveh
CC BY-SA 3.0
2014-02-22T15:05:04.497Z
True, it is indeed unusual to call $NP\neq E$ a separation, as it holds for trivial reasons. I only brought it up to show a simple example where no hierarchy theorem is needed.
Andras Farago
CC BY-SA 3.0
2014-02-26T20:07:32.283Z
Err, the proof of NP!=E *does* depend on a hierarchy theorem!    The way it works is that you first assume NP=E, then use the closure properties of NP to deduce that E=EXP, thereby violating the Time Hierarchy Theorem.
Scott Aaronson
CC BY-SA 3.0
2014-02-27T23:06:23.183Z
Thank you, Scott, you are perfectly right. $NP\neq E$ was not the right example. I posted a better one among the answers.
Andras Farago
CC BY-SA 3.0
2014-02-27T23:43:05.727Z
So even such inequalities rely on diagonalization: $E \subseteq NP \subseteq AC^0\circ NP \subseteq AC^0 \circ E \subseteq EXP$ but $E \subsetneq EXP$. Nice and not so trivial after all.
Kaveh
<cc.complexity-theory><complexity-classes><hierarchy-theorems>
Complexity class separations without hierarchy theorems
Andras Farago
# Complexity class separations without hierarchy theorems

(Asked by: username_0 on 2014-02-22)

Hierarchy theorems are fundamental tools. A good number of them was collected in an earlier question (see [What hierarchies and/or hierarchy theorems do you know?](https://cstheory.stackexchange.com/questions/7303/what-hierarchies-and-or-hierarchy-theorems-do-you-know)). Some complexity class separations directly follow from hierarchy theorems. Examples of such well known separations: $L\neq PSPACE$, $P\neq EXP$, $NP\neq NEXP$, $PSPACE\neq EXPSPACE$.

However, not every separation follows from a hierarchy theorem. A very simple example is $NP\neq E$. Even though we do not know if any of them contains the other, they are still different, because $NP$ is closed with respect to polynomial transformations, while $E$ is not.

Which are some deeper, unconditional, non-relativized complexity class separations for uniform classes that do **not** directly follow from some hierarchy theorem?

**Tags:** cc.complexity-theory, complexity-classes, hierarchy-theorems

> **Comments:**
> **username_1**: I think it is a bit unusual to call $NP\neq E$ a separation. Also their inequality is for trivial reasons and doesn't tell us anything interesting. AFAIK all interesting complexity class separations for large complexity classes rely on hierarchy theorems (and in turn diagonalization) at some point.  
> **username_0**: True, it is indeed unusual to call $NP\neq E$ a separation, as it holds for trivial reasons. I only brought it up to show a simple example where no hierarchy theorem is needed.  
> **username_2**: Err, the proof of NP!=E *does* depend on a hierarchy theorem!    The way it works is that you first assume NP=E, then use the closure properties of NP to deduce that E=EXP, thereby violating the Time Hierarchy Theorem.  
> **username_0**: Thank you, Scott, you are perfectly right. $NP\neq E$ was not the right example. I posted a better one among the answers.  
> **username_1**: So even such inequalities rely on diagonalization: $E \subseteq NP \subseteq AC^0\circ NP \subseteq AC^0 \circ E \subseteq EXP$ but $E \subsetneq EXP$. Nice and not so trivial after all.  

---

## 3 answers

### Answer by username_3 on 2014-02-25. Score: 13

I'd love to be shown wrong, but I don't think there are currently any uniform lower bounds that aren't ultimately based on one of the hierarchy theorems. Our current understanding of how to take advantage of uniformity is really quite limited in that sense.

On the other hand, there are many uniform lower bounds that don't follow *directly* from hierarchy theorems, but use a hierarchy theorem in combination with other clever tricks, techniques, and results, for example:

* $\mathsf{CSL} \not\subseteq \mathsf{DTIME}(n)$ [[Hopcroft-Paul-Valiant](http://dx.doi.org/10.1145/322003.322015)]. They prove that $\mathsf{DTIME}(n) \subseteq \mathsf{DSPACE}(n/\log n)$ (the non-diagonalization part of their proof), and then use the fact that $\mathsf{CSL} = \mathsf{NSPACE}(n)$ in combination with the space hierarchy. Their result + the space hierarchy also implies $\mathsf{DSPACE}(n) \nsubseteq \mathsf{DTIME}(n)$.
* Time-space trade-offs for Satisfiability (see, e.g. the introductions of [Buss-Williams](http://eccc.hpi-web.de/report/2011/031/) and references therein)
* $\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$ [[Paul-Pippinger-Szemeredi-Trotter](http://dx.doi.org/10.1109/SFCS.1983.39)]. Uses a nontrivial simulation of any deterministic super-linear-time machine by a faster four-alternation machine, in combination with the deterministic time hierarchy.
* Uniform lower bounds on the permanant [[Allender](http://dx.doi.org/10.4086/cjtcs.1999.007), [Allender-Gore](http://dx.doi.org/10.1137/S0097539792233907), [Koiran-Perifel](http://dx.doi.org/10.1109/CCC.2009.19)]
* $\mathsf{NEXP} \not\subseteq \mathsf{ACC}^0$ [[Williams](http://dx.doi.org/10.1145/2559903)] (although technically this is a nonuniform lower bound, it uses a bunch of clever ideas in combination with the nondeterministic time hierarchy)


---

### Answer by username_4 on 2014-02-25. Score: 4

Is the separation $\mathsf{AC}^0\subsetneq\mathsf{TC}^0$ by [Smolensky](http://dx.doi.org/10.1145/28395.28404) something you have been looking for?

> **Comments:**
> **username_0**: Thank you, that is a nice result, but I am looking for separations of $uniform$ classes, not circuit classes.  
> **username_5**: @AndresFarago: Uniform AC^0 is also properly included in uniform TC^0.  
> **username_3**: @EmilJeřábek: Is there a proof that uniform $\mathsf{AC}^0$ is properly contained in uniform $\mathsf{TC}^0$ that doesn't also already prove the nonuniform statement? (If not, then it would seem your example falls under the general principle that nonuniform lower bounds are stronger than uniform lower bounds, and I think the OQ was trying to avoid such answers...)  
> **username_1**: I think the nonuniformity in the proofs is secondary to the fact that these are rather small classes where we have some nice combinatorial/algebraic understanding of them. I.e. we understand them well enough to directly construct an object which is not in them. Where are for larger classes there is no such understanding and therefore the only method we know is to do diagonalization against the whole class to construct such objects.  

---

### Answer by username_0 on 2014-02-27. Score: 2

Another nontrivial example comes from the area of average case complexity. Rainer Schuler proves interesting properties of the class he calls $P\_{P-comp}$, see [1].

$P\_{P-comp}$ is the class of languages that are accepted in polynomial time on $\mu$-average for *every* polynomial time computable (P-computable) distribution $\mu$. Naturally, $P\subseteq P\_{P-comp}$ holds, since the existence of a deterministic polytime algorithm implies that it remains efficient on the average, no matter the what the input distribution is. However, the condition of running in average polynomial time for **every** P-computable input distribution appears strong enough to suspect $P\_{P-comp}=P$.

Surprisingly, Schuler proves that there is a language $L\in P\_{P-comp}$, which is Turing-complete for $E$, that is,
$$E\subseteq P^{P\_{P-comp}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; (\*)$$
This implies the unconditional separation $P\_{P-comp}\neq P$. While the latter also uses the fact $E\neq P$, which follows from the Time Hierarchy Theorem, the novel part (\*) builds on different tools: beyond diagonalization, it employs resource bounded measure and Kolmogorov complexity.

Reference:

[1] R. Schuler, "Truth-table closure and Turing closure of average polynomial time have different measures in EXP," CCC 1996, [pdf](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.1686&rep=rep1&type=pdf)

> **Comments:**
> **username_6**: Do not understand. In abstract he says '$\dots$ $P_{P-comp}$ is an example of a subclass of $E\dots$' and so it appears $P_{P-comp}\subseteq E\subseteq P^{P_{P-comp}}$. Is $PSPACE\subseteq P_{P-comp}$?  

---

