1
$\begingroup$

(I've recently started studying satisfiability problems. I've tried to be as clear as possible, but I'm not sure if all of the terminology used is correct.)

Consider a collection of $n$ Boolean variables, $x_1,\ldots,x_n$ and a function $F$ on this collection of variables, $F(x_1,\ldots,x_n)$. An assignment of true and false values to each Boolean variable is called a satisfying assignment if $F(x_1,\ldots,x_n)$ is true.

I'm interested in functions $F$ that take the form $(x_{i_1}\vee x_{j_1} \vee \cdots \vee x_{k_1})\wedge \cdots \wedge (x_{i_m}\vee x_{j_m} \vee \cdots \vee x_{k_m})$ where indices are allowed to repeat, a so-called Monotone k-SAT function. Perhaps something worth noting is that not all of the clauses contain $k$ variables, but it is known that $k$ is the most number of variables in all clauses.

Question: What sort of bounds on the number of satisfying assignments for $F$ are known? The worst bound is $2^n$; I'm hoping there is something better.

(Note: this builds on an original question graciously answered by Yuval Filmus here: Number of states in an AND-OR DAG)

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ A bound in terms of what? If you want an upper bound that depends only on $n$ and $k$, there is no upper bound better than $2^n$: it is easy to construct a formula that has satisfying assignments, so the upper bound $2^n$ is tight. The same for lower bounds (the lower bound of 0 is tight). $\endgroup$
    – D.W. ♦
    Apr 5, 2016 at 21:16

1 Answer 1

Reset to default
2
$\begingroup$

A $k$-SAT instance over $n$ variables, monotone or otherwise, has at most $2^n - 2^{n-k}$ solutions. This is simply the number of possible settings of the $n$ variables minus the least number of settings a single $k$-CNF clause can exclude, assuming all the variables in the clause are distinct. You only have to consider the case of a formula with a single clause because adding more clauses can never increase the number of satisfying assignments.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the response. Do you have a reference for this? Also, a comment above says that $2^n$ is tight, why is this not the case here? $\endgroup$
    – jonem
    Apr 6, 2016 at 22:28
  • $\begingroup$ $2^n$ is a tight upper bound if an empty formula is considered valid, as the convention is that any assignment of the variables satisfies such a formula. There's no reference; the logic of the answer should be straightforward enough that you can verify the truth of it yourself. $\endgroup$
    – Kyle Jones
    Apr 7, 2016 at 2:29

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.