Recently, I am reading paper An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances, which use tree decomposition to give an upper bound for SAT resolution refutation.

For a given nice tree decomposition $T=(V(T),G(T))$.

My question: Why $O(3^{treewidth})*V(T)$ is still $O(3^{treewidth})$

my question comes from the process of proving Theorem 3 from Lemma 2 enter image description here


1 Answer 1


I don't see the claim that $O(3^{tw}) \cdot |V(T)| = O(3^{tw})$, as you mention.

Instead, $O^*(3^{tw}) \cdot |V(T)| = O^*(3^{tw})$. The notation $O^*$ is a shorthand used to suppress polynomial factors in the input size $n$. You should read $O^*(3^{tw})$ as $O(3^{tw} \cdot \text{poly}(n))$.


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.