# Running time of SAT and other EXPTIME algorithms

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^n).$$ 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. 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.

• Double-check the running time of the approach based on SAT. Your claims about that are wrong, I believe.
– D.W.
Commented Sep 10, 2022 at 19:11
• – D.W.
Commented Sep 11, 2022 at 6:05

You have the definition of EXPTIME wrong. The definition refers to the length of the input. Neither $$s$$ nor $$n$$ are the length of the input.
The definition of EXPTIME says that the running time is $$O^{p(\ell)}$$ where $$\ell$$ is the length of the input. A challenge for you: What is the length of the input, in terms of $$s,n$$? Think about what constitutes the input, and how many bits it takes to represent all of the elements of the input.
• Thanks. I wasn't able to delete one post. I am sorry. I do not see how to find the length of the input. I know that for the dynamic programming I used there is a table containing $2^s \cdot n$ inputs, i.e. $n$ rows and $2^s$ columns. Why it counts if numbers are given as binary or unary ? I will also appreciate if you explain the difference between the size and the value or the length of an input. Thanks. Commented Sep 11, 2022 at 8:04
• The algorithm takes as input $n$, the cardinality of the graph, and $s, s\leq n$ the number of colors in the graph. If one keeps $s$ constant, the asymptotic behavior will be linear in terms of $n.$ But if one would increase $s,$ something one would do for the time complexity, then one would necessarily increase also $n$ since $s\leq n.$ Thus in terms of the size of $s$, the runtime will be exponential. I will appreciate your help to explain what is the length of the input in terms of $s$ and $n,$ and about the bits of the input to represent all the elements of the input. Thanks. Commented Sep 18, 2022 at 8:38
• @user153448, another input is the representation of the graph. What is the total length of all those inputs, as a function of $s$ and $n$? How many bits does it take to represent $n$? How many bits does it take to represent $s$? How many bits does it take to represent the graph?