When I try analysing the property of kCNF. I meet a seemingly inessential problem that is more likely to be a combinatorial math problem.

What is the smallest/largest number of clauses where the formula contains them is exact kCNF and has r(or just r=1) satisfying assignment(s) with n variables? To state clearly, for a formula $\mathcal{F}$ where every clause in it is at size k and one or several assignment(s) satisfies(or satisfy) the formula, if we say the number of clauses $\mathcal{F}$ contains is m, the total number of variables is n, what can m be? It is very easy to see how large m it can be at most when r = 1.

I use $SAT_{k,n,r}$ to represent the supremum of m and $sat_{k,n,r}$ to represent the infimum of m temporarily in this question.

When r=1, for simplicity, without loss of generalization, we can set the unique assignment as all-true. Then the largest m could be obtained by enumerating all clauses satisfied by all-true assignment. However, when r>1, it is clear that, the relationship between different satisfying assignments is needed to determine the supremum of m, so this analysis might be much more complicated.

Nevertheless, even if r=1, to consider the infimum of m, what I currently calculate out is... for the case where n=k, $sat_{k,k,1}$=$2^{k}-1$, for the case k=3, I get $sat_{3,n,r}$≤8, well, what about most other cases?

Please notice that kCNF here is exactly containing all clauses at the same size. If we take clauses with smaller size in consideration, then the infimum of m might be a bit harder to consider.


Your Answer

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

Browse other questions tagged or ask your own question.