7
$\begingroup$

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?

$\endgroup$
3
  • 6
    $\begingroup$ The input size is the number of bits required to represent the input. $\endgroup$
    – Jeffε
    Aug 26, 2013 at 2:29
  • 1
    $\begingroup$ does it matter, given that the two parameters you mention are polynomially related and are themselves polynomially related to the size of any reasonable representation of a 3CNF (which, as Jeff said, is the parameter in formal definition of complexity classes) $\endgroup$ Aug 26, 2013 at 2:46
  • $\begingroup$ Sasho: I can see now that maybe I have to change my question. "Which is a reasonable representation of a 3CNF?" This is what I am not understanding. $\endgroup$
    – pablo1977
    Aug 26, 2013 at 3:17

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ The details of your answer are what I really need to understand this matter. Thanks. $\endgroup$
    – pablo1977
    Aug 27, 2013 at 14:29
  • 1
    $\begingroup$ The $4N^3$ bit representation above is for exact-3SAT. By using $2^k$ index strings, one for each pattern of negations in a $k$-clause, and enumerating the choice of sets of $k=1,2,3$ variables out of $N$, the representation can be reduced to $(4/3)N^3(1−(3N−1)/2N^2) \le (4/3)N^3$ bits. This representation allows only one occurrence of any variable in each clause, removes the permutation redundancy, and allows clauses containing 1 or 2 literals. $\endgroup$ Mar 13, 2017 at 10:47
2
$\begingroup$

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)$

$\endgroup$
4
  • 1
    $\begingroup$ There are at most $8m^3$ distinct clauses, do you mean formulas where the same clause is repeated multiple times? I guess that's a fair point. But your bound on the encoding size is wrong, you must mean $O(k \log k)$, which is tight by a counting argument. $\endgroup$ Aug 26, 2013 at 16:44
  • 1
    $\begingroup$ Yep. If the instance come from a concrete problem, one may have a formula with some repeated clauses. And you're right for the encoding, $\log m$ for one clause, times the number of clauses, giving $k \log k$ $\endgroup$
    – Tpecatte
    Aug 26, 2013 at 17:01
  • 1
    $\begingroup$ @SashoNikolov Thanks for your answers. Perhaps I have to be more precise in my question. I've read that in 3SAT problem is supposed that one takes terms with no repetitions. Thus, $k < cm^3$ it would be a good estimate. $\endgroup$
    – pablo1977
    Aug 27, 2013 at 5:11
  • 1
    $\begingroup$ In this case, as Sasho said, both are polynomially related since $m < 3k$ and $k < cm^3$, hence you can chose either $k$ or $m$ as parameter of the input. $\endgroup$
    – Tpecatte
    Aug 27, 2013 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.