We say an algorithm runs in polynomial time if it is of the form $O(n^k)$ where $n$ is the size of the input, right?

So how do we judge how many inputs there are in: $(x_1 \vee x_2 \vee \overline{x_3}) \wedge (\overline{x_1} \vee \overline{x_2} \vee x_4) \wedge (x_2\vee x_3\vee x_5)$

...actually, in looking for an actual definition of an algorithm running in polynomial time, wolframAlpha says: "An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is $O(n^k)$ for some non-negative integer $k$, where $n$ is the complexity of the input. "

So, then my question is, for my example, what is the complexity of the input? Is the complexity based on how many variables, or how many clauses?

  • 3
    $\begingroup$ I'm not sure what you're asking. The SAT problem has inputs (formulae we want to test for satisfiability) and the Boolean formula has variables. I've never heard the word "input" used to mean some parameter of the formula used as an input to the SAT problem: in what context did you come across this? $\endgroup$ – David Richerby Oct 3 '15 at 6:45
  • $\begingroup$ There is one input. $\endgroup$ – Yuval Filmus Oct 3 '15 at 8:07
  • 2
    $\begingroup$ "where n is the complexity of the input" -- that's a horrible way of putting things. $n$ is just the length of a (reasonable) encoding of the input, i.e. the string you put on the TM tape. Yes, the specific encoding can matter so you have to fix it. $\endgroup$ – Raphael Oct 4 '15 at 10:25

The complexity of SAT relates to the number of arguments to the Boolean function (i.e. the "distinct literals" in the expression), not the number of terms in a particular normal form.

The complexity of an algorithm which solves SAT is related to the size of the input that you give it. So if the input is the Unicode string (x1∨x2∨¬x3)∧(x1¬∨x2¬∨x4)∧(x2∨x3∨x5), then the size of that is the number of Unicode codepoints (or bytes or bits used to encode those codepoints).

The subject of SAT is the function, not the representation of the function. The complexity class (i.e. the complexity of any solver which is optimal for its computer) is the same whether functions are written as product-of-sums or a sum-of-products. This complexity varies with the number of arguments to the function.

The input to a SAT solver is the representation of the function. Your example is in the product-of-sums normal form, which is a common way to express SAT problems. This is not a coincidence — SAT is solved mindlessly if you instead give it a sum-of-products expression! The brute-force method of solving SAT is to enumerate the sum-of-products, where each term either contradicts itself (b ¬b) or represents a satisfied piece of the function's domain. This simple approach doesn't trivialize SAT because going from one normal form to the other causes a combinatorial explosion. The size of the domain of a function of $n$ Boolean arguments is $2^n$.

Thus, feeding a gigantic problem description into a simple algorithm may have the same computational (and space) complexity as feeding a simple but equivalent description into a sophisticated algorithm. For brevity, we tend to prefer to imagine the description to be simple and the algorithm to be complicated.

  • 1
    $\begingroup$ Your last paragraph is very unclear. Computational complexity is measured as a function of the input length so I don't understand what you mean by saying that one problem with a small input might have the same complexity as another problem with a large input. It doesn't make sense to talk about the complexity of a problem for a particular input length: complexity is how the resource requirements change as the input length changes. $\endgroup$ – David Richerby Oct 3 '15 at 10:24
  • 2
    $\begingroup$ "SAT is a class of algorithms" No, SAT is a computational problem. $\endgroup$ – David Richerby Oct 3 '15 at 14:12
  • 2
    $\begingroup$ You are confusing "complexity" as measure of intuitive hardness of something with "(computational) complexity" as a well-defined, mathematical measure of computational (!) problems. $\endgroup$ – Raphael Oct 4 '15 at 10:28
  • 2
    $\begingroup$ Please consolidate this discussion in the form of improving edits, or continue it in chat. I'll expect some "obsolete" flags! Thank you. (cc @DavidRicherby) $\endgroup$ – Raphael Oct 4 '15 at 10:29
  • 3
    $\begingroup$ A problem is defined with respect to a particular representation of the input. The exact representation is often left out because “reasonable” representations are equivalent with respect to the complexity classes we usually study, but it does matter. For example, SAT is defined over arbitrary formulas, not only formulas in some normal form, and this matters. It isn't about the size of the input: the explosion in size if we pick a normal form is just a hint that the problem may not be in P. $\endgroup$ – Gilles 'SO- stop being evil' Oct 4 '15 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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