patternMinor
Input size of 3-SAT when analyzing complexity
Viewed 0 times
satsizeanalyzinginputwhencomplexity
Problem
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?
Solution
At the most basic level, the size of the input is the length of the string that encodes the input given to the Turing Machine - i.e. the number of cells it takes up on the tape under the chosen encoding scheme.
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.
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.
Context
StackExchange Computer Science Q#10224, answer score: 3
Revisions (0)
No revisions yet.