<p><span class="math-container">$O(n^2 \cdot 2^s) = O(2^{\log_2(n^2)} \cdot 2^s) = O(2^{s+2log_2(n)})$</span>, so your provided runtime is still in <span class="math-container">$EXPTIME$</span> as long as <span class="math-container">$n \in 2^{O(\text{poly}(s))}$</span>.</p>
<p>For your second question, I'm not entirely sure what you mean. <span class="math-container">$EXPTIME$</span> contains languages recognizable in <span class="math-container">$\Theta(1)$</span> time, so certainly <span class="math-container">$O(2^n)$</span> isn't a lower bound for <span class="math-container">$EXPTIME$</span> problems. Maybe you mean algorithms that are in <span class="math-container">$EXPTIME$</span> but not a smaller class like <span class="math-container">$P$</span>. But no, there are plenty of <span class="math-container">$EXPTIME$</span> problems with a runtime of e.g. <span class="math-container">$\Theta(2^\sqrt{n})$</span>. The Time Hierarchy Theorem ensures that.</p>

CC BY-SA 4.0
2022-09-10T20:36:25.287Z
2022-09-10T20:36:25.287Z
Jake
<p>I need to propose an algorithm for a NP-hard problem. I use dynamic programming which leads to a running time <span class="math-container">$O(2^s\cdot n^2), s\leq n.$</span> The algorithm aims to finding a path in a graph <span class="math-container">$G(V, E)$</span> (in which each of the n nodes is colored in one of the <span class="math-container">$s$</span> colors) containing all the <span class="math-container">$s$</span> colors which are represented a single time in the path. If we take a SAT solver approach, we get an exponential running time <span class="math-container">$O(2^s).$</span> I do not know if the running time of the SAT is correct, i.e. I do not see if I miss a polynomial factor such as <span class="math-container">$n^2$</span> which I get by the dynamic programming. I want to understand the difference in the running time of the two approaches. First, I have a naive question.</p>
<p>The time complexity <span class="math-container">$O(2^s\cdot n^2)$</span> contains a polynomial term. It is clear that <span class="math-container">$2^s = O(2^s\cdot n^2).$</span> Can we say that <span class="math-container">$O(2^s\cdot n^2)$</span> remains exponential even though it contains a polynomial term ?</p>
<p>By definition of the EXPTIME algorithms we know that the running time is <span class="math-container">$O(2^{p(s)})$</span> where <span class="math-container">$p(s)$</span> is polynomial. This is in line with the SAT but not with the one I get from the dynamic programming. Can one maybe claim that the SAT provides the lower bound of EXPTIME algorithms ? Thanks.</p>

CC BY-SA 4.0
2022-09-11T06:05:23.413Z
Cross-posted: https://cs.stackexchange.com/q/154077/755, https://cstheory.stackexchange.com/q/51861/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<cc.complexity-theory><np-hardness><sat>
Running time of SAT and other EXPTIME algorithms
user67418
# Running time of SAT and other EXPTIME algorithms

(Asked by: username_0 on 2022-09-10)

I need to propose an algorithm for a NP-hard problem. I use dynamic programming which leads to a running time $O(2^s\cdot n^2), s\leq n.$ The algorithm aims to finding a path in a graph $G(V, E)$ (in which each of the n nodes is colored in one of the $s$ colors) containing all the $s$ colors which are represented a single time in the path. If we take a SAT solver approach, we get an exponential running time $O(2^s).$ I do not know if the running time of the SAT is correct, i.e. I do not see if I miss a polynomial factor such as $n^2$ which I get by the dynamic programming. I want to understand the difference in the running time of the two approaches. First, I have a naive question.

The time complexity $O(2^s\cdot n^2)$ contains a polynomial term. It is clear that $2^s = O(2^s\cdot n^2).$ Can we say that $O(2^s\cdot n^2)$ remains exponential even though it contains a polynomial term ?

By definition of the EXPTIME algorithms we know that the running time is $O(2^{p(s)})$ where $p(s)$ is polynomial. This is in line with the SAT but not with the one I get from the dynamic programming. Can one maybe claim that the SAT provides the lower bound of EXPTIME algorithms ? Thanks.

**Tags:** cc.complexity-theory, np-hardness, sat

> **Comments:**
> **username_1**: Cross-posted: https://cs.stackexchange.com/q/154077/755, https://cstheory.stackexchange.com/q/51861/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 1 answers

### Answer by username_2 on 2022-09-10. Score: 2

$O(n^2 \cdot 2^s) = O(2^{\log\_2(n^2)} \cdot 2^s) = O(2^{s+2log\_2(n)})$, so your provided runtime is still in $EXPTIME$ as long as $n \in 2^{O(\text{poly}(s))}$.

For your second question, I'm not entirely sure what you mean. $EXPTIME$ contains languages recognizable in $\Theta(1)$ time, so certainly $O(2^n)$ isn't a lower bound for $EXPTIME$ problems. Maybe you mean algorithms that are in $EXPTIME$ but not a smaller class like $P$. But no, there are plenty of $EXPTIME$ problems with a runtime of e.g. $\Theta(2^\sqrt{n})$. The Time Hierarchy Theorem ensures that.


---

