<p>Here's one involving a 2 player pebble game. You decide if it's <em>natural</em> (:</p>

<p><a href="http://epubs.siam.org/doi/abs/10.1137/0208046">T. Kasai, A. Adachi, S. Iwata. Classes of pebble games and complete problems. 1979</a></p>

<p>Theorem 3.1 has the EXPTIME-completeness of pebbling. Theorem 3.3 has the easiness of k-pebble.</p>

<p><a href="http://dl.acm.org/citation.cfm?id=322433">A. Adachi, S. Iwata, T. Kasai. Some Combinatorial Game Problems Require Omega(n^k) Time. 1984</a></p>

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

<p><a href="http://link.springer.com/article/10.1007%2FBF01699467">T. Kasai and S. Iwata. Gradually intractable problems and nondeterminitstic log-space lower bounds. 1985</a></p>

<p>Sadly that these are all behind paywalls :(</p>

CC BY-SA 3.0
2015-11-14T18:20:06.917Z
This is wonderful!  Thank you very much.  :)
Michael Wehar
CC BY-SA 3.0
2015-11-14T08:13:05.163Z
2015-11-14T09:14:02.123Z
2015-11-14T09:14:02.123Z
Whosyourjay
<p>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.</p>

<p><strong>Exponential Lower Bounds:</strong></p>

<p><em>Claim:</em> 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.  </p>

<p><em>Proof Idea:</em> 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.</p>

<p><strong>Polynomial Lower Bounds:</strong></p>

<p>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:</p>

<ul>
<li>For each fixed $k$, $k$-$X$ is in polynomial time.</li>
</ul>

<p>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.</p>

<p><strong>An Example:</strong></p>

<p>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?</p>

<p>This problem was shown to be $EXPTIME$-complete <a href="http://research.microsoft.com/apps/pubs/default.aspx?id=78382" rel="noreferrer">here</a>.  Further, we can parameterize the intersection problem by the number of automata $k$.  It can be <a href="http://link.springer.com/chapter/10.1007%2F978-3-662-47666-6_33" rel="noreferrer">shown</a> that for fixed $k$, the intersection problem has time complexity $n^{\Theta(k)}$.</p>

<p><strong>Question:</strong></p>

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

<cc.complexity-theory><complexity-classes><time-complexity><lower-bounds><polynomial-time>
Are there more polynomial time problems with complexity lower bounds?
Michael Wehar
# Are there more polynomial time problems with complexity lower bounds?

(Asked by: username_0 on 2015-11-12)

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](http://research.microsoft.com/apps/pubs/default.aspx?id=78382). Further, we can parameterize the intersection problem by the number of automata $k$. It can be [shown](http://link.springer.com/chapter/10.1007%2F978-3-662-47666-6_33) 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?

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, lower-bounds, polynomial-time

---

## 1 answers

### Answer by username_1 on 2015-11-14. Score: 5 | Accepted answer

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](http://epubs.siam.org/doi/abs/10.1137/0208046)

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](http://dl.acm.org/citation.cfm?id=322433)

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](http://link.springer.com/article/10.1007%2FBF01699467)

Sadly that these are all behind paywalls :(

> **Comments:**
> **username_0**: This is wonderful!  Thank you very much.  :)  

---

