# Are there more polynomial time problems with complexity lower bounds?

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

Question:

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

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 :(

• This is wonderful! Thank you very much. :) Nov 14 '15 at 18:20