Is there an extension of SAT with variables $x_1, ..., x_n$ and clauses $C$ where the truth assignments must satisfy monotonicity over the variables in the sense that $x_1 \le x_2 \le \ldots \le x_n$ where 0 = False and 1 = True? If so, what is its complexity?

For example, if n = 3, the SAT problem would only be true if one of the following truth assignments satisfied each clause: $(x_1,x_2,x_3) \in \{\{0,0,0\},\{0,0,1\},\{0,1,1\},\{1,1,1\}\}$.


1 Answer 1


We can certainly define such an extension.

We usually don't, because it's very easy to solve. An $n$-variable instance only has $n+1$ possible truth assignments, so we can can just check them all.

In particular, it's polynomial time. The algorithm above is quadratic in the input length, since you can check a truth assignment in time proportional to the number of clauses. Maybe there are other, faster algorithms.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .