17
$\begingroup$

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?). 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?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Feb 22, 2014 at 5:44
  • $\begingroup$ 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. $\endgroup$
    – Andras Farago
    Feb 22, 2014 at 15:05
  • 3
    $\begingroup$ 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. $\endgroup$
    – Scott Aaronson
    Feb 26, 2014 at 20:07
  • $\begingroup$ Thank you, Scott, you are perfectly right. $NP\neq E$ was not the right example. I posted a better one among the answers. $\endgroup$
    – Andras Farago
    Feb 27, 2014 at 23:06
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Feb 27, 2014 at 23:43

3 Answers 3

Reset to default
13
$\begingroup$

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]. 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 and references therein)
  • $\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$ [Paul-Pippinger-Szemeredi-Trotter]. 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, Allender-Gore, Koiran-Perifel]
  • $\mathsf{NEXP} \not\subseteq \mathsf{ACC}^0$ [Williams] (although technically this is a nonuniform lower bound, it uses a bunch of clever ideas in combination with the nondeterministic time hierarchy)
Improve this answer
$\endgroup$
4
$\begingroup$

Is the separation $\mathsf{AC}^0\subsetneq\mathsf{TC}^0$ by Smolensky something you have been looking for?

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thank you, that is a nice result, but I am looking for separations of $uniform$ classes, not circuit classes. $\endgroup$
    – Andras Farago
    Feb 25, 2014 at 13:23
  • 2
    $\begingroup$ @AndresFarago: Uniform AC^0 is also properly included in uniform TC^0. $\endgroup$
    – Emil Jeřábek
    Feb 25, 2014 at 20:08
  • 2
    $\begingroup$ @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...) $\endgroup$
    – Joshua Grochow
    Feb 25, 2014 at 21:45
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Feb 27, 2014 at 23:26
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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}$? $\endgroup$
    – Turbo
    Jan 3, 2021 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.