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?
Are there more polynomial time problems with complexity lower bounds?
cc.complexity theory;complexity classes;time complexity;lower bounds;polynomial time
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. 1979Theorem 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. 1984Theorem 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. 1985Sadly that these are all behind paywalls :(