Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
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))$.
