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 x1, ..., xm.
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) ).

I am in trouble with this simple issue.

---

According to the answer of Timmie Smith, we can consider the estimate:

k <= constant * f(m)

where m is a polynomial function of m.
More precisely, the function P(m) it could be considered of exponent 3 (that is, cubic).

Thus, if we consider the complexity f(k) of 3-SAT, we would have:

f(k, m)=f(P(m),m), (with P(m) = m^3).

So, if the function f is polyonomial in k and m, then actually results polynomial in m. Thus, by considering m as the input size, it would be to estimate if a given algorithm is, or not, polynomial in m, in order to know if 3-SAT is in P or not.

If you agree, I can accept the answer of Timmie as the good one.

UPDATE:

I did the same question here:

https://cstheory.stackexchange.com/questions/18756/whats-the-meaning-of-input-size-for-3-sat

The accepted answer was helpful to me.

Answer 1

The input is the number m of variables. This is because the number of possible clauses that can be formed given m variables is a polynomial function of the number of variables.

Answer 2

The input size is the number of variables m.

The reason for this is that the size of the search space that needs to be traversed for solving the problems is determined entirely by the number of variables: Each variable has two possible states (1 or 0), the search space consists of all possible assignments. A brute-force algorithm would just test all possible assignments (2^m) to traverse the search space. Although most 3-SAT algorithms will be impacted significantly by the number of clauses, that does not influence the underlying problem's complexity.

Therefore the input size is also the number of variables for plain-old SAT, where the search space looks the same, although resolving clauses in a non-brute-force way works quite differently.

Answer 3

I've seen in some papers of Carnegie Mellon University the following definition of "size of input" for this kind of problems:

number of bits it takes to write the input down

Considering that the input can be compressed, this definition makes sense to me, because it is a good measure of input entropy.

My 2 cents! Cheers!!