A precise statement of: "The boolean satisfiability problem (SAT) is in NP"

67 Views Asked by At

If $f$ is a function $\mathbb N\to\{\text{True},\text{False}\}$, then I know what it means to say that $f$ is in NP. But if $f$ is a function $A\to \{\text{True},\text{False}\}$, where $A$ is a set, then I do not know what that means.

The Boolean satisfiability problem (SAT) is known to be in NP, but what exactly does that mean? The domain $A$ of SAT is the set of all propositional-logic-formulas. Have people agreed to use some specific function $A\to\mathbb N$ as an encoding?

1

There are 1 best solutions below

9
On BEST ANSWER

In fact your premise is mistaken. Complexity classes like P, NP, and NPC are defined for decision problems on sets of strings, not sets of numbers. (Sets of strings are called “languages” in the jargon.)

The concept can easily be extended to sets of numbers because numbers can be encoded as strings. For example the number $119$ can be encoded as the string 119 or as 1110111.

Similarly formulas are easily encoded as strings. For example the formula $(a\land b)\lor(\lnot a\land c)$ can be encoded as the string (a∧b)∨(¬a∧c).

The exact details of the encoding we choose are not really important, as long as the length of the string is.polynomial in the “size” of the problem. Sometimes this is important but usually we can ignore the details.

The Garey and Johnson book has a more detailed discussion of this point, but they will tell you the same thing. Encoding formulas or graphs as strings is no different in principle than encoding numbers as strings.