Running time of SAT and other EXPTIME algorithms [closed]

Question

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.

Answer 1

$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.