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?
