What's the meaning of "input size" for 3-SAT?

Question

In the computational complexity theory, we say that an algorithm have complexity $O(f(n))$ if the number of computations that solve a problem with input size $n$ is bounded by $cf(n)$, for all integer $n$, where $c$ is a positive constant non-depending on $n$, and $f(n)$ is an increasing function that goes to infinity as $n$ does.

The 3-SAT problem is stated as: given a CNF expression, whose clauses has exactly 3 literals, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true?

A CNF expression consists of, say, $k$ clauses involving m variables $x_1,x_2, ..., x_m$.
In order to decide if 3-SAT has polynomial complexity $p(n)$, or not, I need to understand something so simple as "what is n" in the problem.

My question is:

Which is considered, in this particular 3-SAT problem, the input size n?

Is it the number k of clauses? Or is it the number m of variables?
Or n is some function of k and m? ( $n=f(k,m)$ ).

What exactly the theoretical computer scientits consider as the input size for this problem?

I did the estimate that $n \leq $constant $* m^3$. Is this correct for you?

Answer 1

In complexity theory, $n$ is the length in bits of the input the algorithm has been given.

In particular, it is not the "number of bits required to represent the input" because that would be very hard to reason about — you'd have to prove that you'd chosen the most efficient possible coding. If my input to 3-SAT is the formula consisting of 276 repetitions of the clause $X\vee \neg Y \vee \neg Z$, then $n$ is however many bits it took me to express that input; it is not, for example, the number of bits it would have taken me to express the equivalent formula that has just one copy of the clause.

Now, in practical terms, complexity is often expressed in terms of other measures. For example, the running time of algorithms in graph theory is often given as a function of the number of vertices and/or edges; in satisfiability, the number of variables and/or clauses is often used. In terms of describing algorithms, it's often more intuitive to give the bounds that way: it's a higher-level view of a graph as a set of vertices and edges, rather than the "machine-code" view of representing that as a string of bits. In terms of complexity theory, we're often only interested in broad questions like, "Is there a polynomial-time algorithm?" or "Does it need exponential time?" Because these questions are insensitive to polynomial factors, $n$ is sometimes used to mean other things. For example, in 3-SAT, a formula in $N$ variables can be coded using $n=4N^3$ bits (see below). Anything that's polynomial in $n$ is polynomial in $N$ and vice-versa so, for that kind of question, it doesn't really matter which you use.

Here's how to code a 3-CNF formula with $N$ variables in $4N^3$ bits. Every clause has either 0, 1, 2 or 3 negations; we may permute so that the negated literals appear first in any clause. Now, fix an enumeration (say, lexicographic) of all the $N^3$ possible 3-tuples of variables. For each kind of clause (0, 1, 2 or 3 negations), make a list of $N^3$ bits such that the $i$th bit is 1 if, and only if, the $i$th 3-tuple is a clause with that number of negations. The input is those four lists. The first thing any algorithm using this input format would do is check that its input length is $4N^3$ for some $N$. If it isn't, the input doesn't code anything, so it doesn't code a satisfiable formula, so the algorithm rejects.

Note that even the above coding still has some redundancy, since the clause $X\vee Y \vee Z$ appears in six permutations. If $n$ were the minimum number of bits required to code the input, we'd be forced to use a coding that avoided that redundancy. Worse, if we were reasoning about 3-SAT over random inputs selected from some distribution, the minimum number of bits required to express some input would involve something like Huffman coding the inputs according to that distribution, and it would be a total nightmare. So it's just the length of the input you were given.

Answer 2

Sasho : that's not completely true, you seem to assume that the formula doesn't have any redundant clause. A formula could have exponentially many 3-clauses in the number of variables. Thus, it might be better to consider $k$ as main parameter.

Then, I think that any reasonable encoding will have the same size, which will be roughly $O(k \log m)$. And because $m < 3k$, we end up with an encoding in $O(k \log k)$.

EDIT: encoding is of size $O(k \log k)$ and not $O(\log^2 k)$