<p>Given a Turing machine $T$ and an a number $n$ encoded in unary, decide whether $T$ halts in time $2^n$. There is an $O(C^n)$ algorithm for this, and there's an almost matching $\Omega(c^n)$ lower bound (where $c &lt; C$). See the proof of the <a href="http://en.wikipedia.org/wiki/Time_hierarchy_theorem">Time Hierarchy Theorem</a>.</p>

<p>If you're looking for more natural problems, Wikipedia has a list of <a href="http://en.wikipedia.org/wiki/EXPTIME">EXPTIME-complete problems</a>, such as evaluating positions in certain generalized versions of board games, and problems involving succinct circuits.</p>

CC BY-SA 3.0
2015-01-17T15:18:06.390Z
2015-01-17T15:18:06.390Z
Yuval Filmus
<p>I am looking for problems which have an algorithm with asymptotically optimal exponential computational complexity or the problem has a lower bound of exponential computational complexity for algorithms to solve the problem.</p>

<p>I am not looking for problems, where this is implied because the solution can be exponential in size.</p>

<p>If you know any, it would be very kind if you can share it with me.</p>

CC BY-SA 3.0
2015-01-17T14:58:08.670Z
Have you looked at $EXPTIME$-complete problems and the time hierarchy theorem?  Do these not fit your needs?
Tom van der Zanden
CC BY-SA 3.0
2015-01-17T15:09:44.297Z
Do you have a link to a list of exptime-complete problems? i don't find any
user3680510
CC BY-SA 3.0
2015-01-17T17:30:13.533Z
Given a multi-stack pushdown automaton M with bounded phase switches, does there exist a string x such that M accepts x?  Let n denote the size of M and k denote the number of phase switches. We can solve this problem in $n^{2^k}$ time, but we can't solve it in $n^{o(2^k)}$ time.  I just thought this was an interesting and less artificial example.  If interested, please let me know and I can provide more info.
Michael Wehar
CC BY-SA 3.0
2015-01-17T21:39:01.033Z
yes sounds interesting. Is this problem in NP?
user3680510
CC BY-SA 3.0
2015-01-17T22:08:35.507Z
There is no problem in NP which in known to requires exponential time. Also the size of output for decision problems is 1 bit (yes or no).
Kaveh
CC BY-SA 3.0
2015-01-31T01:43:08.683Z
@user3680510 For fixed k, this problem is in P.  If k is dependent on n, then it is known to be in double exponential time.  If you're interested, I can provide a link to more details on the problem.  :)
Michael Wehar
<complexity-classes>
Problems with exponential lower computational complexity bound
user3680510
# Problems with exponential lower computational complexity bound

(Asked by: username_0 on 2015-01-17)

I am looking for problems which have an algorithm with asymptotically optimal exponential computational complexity or the problem has a lower bound of exponential computational complexity for algorithms to solve the problem.

I am not looking for problems, where this is implied because the solution can be exponential in size.

If you know any, it would be very kind if you can share it with me.

**Tags:** complexity-classes
> **Comments:**
> **username_1**: Have you looked at $EXPTIME$-complete problems and the time hierarchy theorem?  Do these not fit your needs?  
> **username_0**: Do you have a link to a list of exptime-complete problems? i don't find any  
> **username_2**: Given a multi-stack pushdown automaton M with bounded phase switches, does there exist a string x such that M accepts x?  Let n denote the size of M and k denote the number of phase switches. We can solve this problem in $n^{2^k}$ time, but we can't solve it in $n^{o(2^k)}$ time.  I just thought this was an interesting and less artificial example.  If interested, please let me know and I can provide more info.  
> **username_0**: yes sounds interesting. Is this problem in NP?  
> **username_3**: There is no problem in NP which in known to requires exponential time. Also the size of output for decision problems is 1 bit (yes or no).  
> **username_2**: @user3680510 For fixed k, this problem is in P.  If k is dependent on n, then it is known to be in double exponential time.  If you're interested, I can provide a link to more details on the problem.  :)  

---

## 1 answers

### Answer by username_4 on 2015-01-17. Score: 6

Given a Turing machine $T$ and an a number $n$ encoded in unary, decide whether $T$ halts in time $2^n$. There is an $O(C^n)$ algorithm for this, and there's an almost matching $\Omega(c^n)$ lower bound (where $c < C$). See the proof of the [Time Hierarchy Theorem](http://en.wikipedia.org/wiki/Time_hierarchy_theorem).

If you're looking for more natural problems, Wikipedia has a list of [EXPTIME-complete problems](http://en.wikipedia.org/wiki/EXPTIME), such as evaluating positions in certain generalized versions of board games, and problems involving succinct circuits.


---

