# Input size of 3-SAT when analyzing complexity

We know that $\text{3-SAT}$ problem is NP-complete, but I am not sure what is meant by size of input. Does this mean number of literals, or number of variables?

## migrated from cstheory.stackexchange.comMar 3 '13 at 10:41

This question came from our site for theoretical computer scientists and researchers in related fields.

In practice though, we often measure the size of the input via proxy measurements. So for problems like 3-SAT, we might choose the number of variables or the number of clauses as a proxy for the size of the input. Another example is for many graph based problem the number of vertices is chosen as a proxy for the size of the input, even though the length of the encoding of a graph may be something more like $O(|V|^{2}\log|V|)$. Note that this is polynomial in $|V|$, so when we are considering polynomial time algorithms or reductions, the polynomial factor between the proxy and the actual size poses no problem.