In this variant of #Positive-2-SAT ,we divide set of all possible clauses like this :

A = [ab ,ac ,ad ,.... ]

B =[bc ,bd ,be ,....]

C=[cd ,de ,....]

D=[de ,....]


In this variant ,we are allowed to select clauses from only 3 sets mentioned ,And for every k variable there are k such sets but for k variables ,we are only allowed to select clauses from any three of these k sets ,then , is counting the number of satsifiable instance of these clauses #P-complete or not.

If its not #P-complete for where we are allowed to select clauses from only 3 sets ,then does there exist a value k ,such that we are allowed to select clauses from only k sets ,for which this problem is #P-complete?

This problem is inspired from my previous problem ,here the restriction are vertical ,In my previous problem restriction was horizontal ,in a sense that we select clauses from every set but only a certain amount ,but here we can choose as many as we want but from a limited number of sets


1 Answer 1


The problem is in P for any fixed $k$. The clauses shouldn't need to be all positive, either.

For the positive example, let's say we choose from sets $A$, $B$ and $C$ (it doesn't really matter). For each of the 8 (or generally, $2^k$) possible truth assignments to $a$, $b$ and $c$ (which I will call the main variables), the number of satisfying assignments is simply $2^s$, where $s$ is the number of variables (obviously excluding the main variables themselves) that only occur in clauses where the main variable of that clause is chosen to be true.

You have to mind the existence of clauses like $(a \vee b)$, but they don't really complicate the picture - just set the number of satisfiable assignments to 0 for every assignment of the main variables where both $a$ and $b$ are chosen to be false.

  • $\begingroup$ Can you explain a bit more with example if possible? $\endgroup$
    – Anuj
    Jun 24, 2023 at 3:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.