I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below.

Exponential Lower Bounds:

Claim: If you have a problem $X$ that is $EXPTIME$-complete under polynomial reductions, then there is a constant $\alpha \in \mathbb{R}$ such that $X$ is not solvable in $O(2^{n^{\alpha}})$ time.

Proof Idea: By the time hierarchy theorem, there is a problem $Y$ in $O(2^n)$ time that is not in $o(\frac{2^n}{n})$ time. Further, there must be a polynomial reduction from $Y$ to $X$. Therefore, there is a constant $c$ such that this reduction takes an instance of size $n$ for $Y$ to an instance of size $n^c$ for $X$. The lower bound for $Y$ of $O(2^{n^{1-\epsilon}})$ time shifts to a lower bound for $X$ of $O(2^{n^{\frac{1-\epsilon}{c}}})$ time.

Polynomial Lower Bounds:

Some $EXPTIME$-complete problems have nice parameterizations into polynomial time problems. Consider the problem $X$ from before. Suppose we have a parameterization $k$-$X$ for $X$ such that:

  • For each fixed $k$, $k$-$X$ is in polynomial time.

There are of course exceptions to this, but intuitively, as $k$ grows the $k$-$X$ problems should get harder because $X$ has an exponential time complexity lower bound.

An Example:

One example problem that has come up is intersection non-emptiness for tree automata. That is, given a finite list of tree automata, does there exist a tree that simultaneously satisfies all of the automata?

This problem was shown to be $EXPTIME$-complete here. Further, we can parameterize the intersection problem by the number of automata $k$. It can be shown that for fixed $k$, the intersection problem has time complexity $n^{\Theta(k)}$.


Are there any other $EXPTIME$-complete problems that have natural parameterizations into polynomial time problems with nice lower bounds?


1 Answer 1


Here's one involving a 2 player pebble game. You decide if it's natural (:

T. Kasai, A. Adachi, S. Iwata. Classes of pebble games and complete problems. 1979

Theorem 3.1 has the EXPTIME-completeness of pebbling. Theorem 3.3 has the easiness of k-pebble.

A. Adachi, S. Iwata, T. Kasai. Some Combinatorial Game Problems Require Omega(n^k) Time. 1984

Theorem 3.2 has the lower bound on k-pebble. Lastly, you might also be interested in:

T. Kasai and S. Iwata. Gradually intractable problems and nondeterminitstic log-space lower bounds. 1985

Sadly that these are all behind paywalls :(

  • $\begingroup$ This is wonderful! Thank you very much. :) $\endgroup$ Nov 14, 2015 at 18:20

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.