16
$\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?

$\endgroup$
  • 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 '14 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 '14 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 '14 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 '14 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 '14 at 23:43
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)
$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 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 '14 at 13:23
  • 2
    $\begingroup$ @AndresFarago: Uniform AC^0 is also properly included in uniform TC^0. $\endgroup$ – Emil Jeřábek Feb 25 '14 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 '14 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 '14 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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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