0
$\begingroup$

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.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – user153448
    Commented Sep 11, 2022 at 8:04
  • $\begingroup$ @user153448, not the table used by the algorithm, but the input to the algorithm. What are the inputs to the algorithm? What quantities does the algorithm take as input? If you're not sure, then maybe try to write pseudocode (or real code) for the algorithm. That will force you to identify the inputs explicitly. $\endgroup$
    – D.W. ♦
    Commented Sep 11, 2022 at 22:23
  • $\begingroup$ 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. $\endgroup$
    – user153448
    Commented Sep 18, 2022 at 8:38
  • $\begingroup$ @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? $\endgroup$
    – D.W. ♦
    Commented Sep 18, 2022 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.