# Running time of SAT and other EXPTIME algorithms [closed]

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.

• – D.W.
Sep 11, 2022 at 6:05

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