0
$\begingroup$

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\}\}$.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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