Complexity of a variant of #Positive-2-SAT

Question

#Positive-2SAT is the problem of counting the number of satisfying assignments to a given Positive 2-CNF formula i.e 2-CNF formulas in which each literal is a positive occurrence of a variable.

The following variant of #Positive 2-SAT is defined as follows :

For example ,We are given a set of variables :

(a,b,c,d,e)

The set of all possible positive 2-literal clauses from the given set of variables are :

• A = [ ab ,ac ,ad ,ae ]
• B = [ bc ,bd ,be ]
• C = [ cd ,ce ]
• D = [ de ]

This version of problem puts restrictions on the inputs such that we can only choose at max only two clause from each set mentioned above to form our set of input clauses.

Ex-

1. A valid input to this variant of #Positive 2-SAT would be (ab ,ac ,bc ,cd) here we have only at max 2 clauses form each set mentioned above.
2. An invalid input to this variant of #Positive 2-SAT would be (ac ,ad ,ae ,bc ,cd) this is invalid as we have chosen more than 2 clauses from set A, mentioned above, thus its not a valid input to this version of the problem as we must only choose at max 2 clause form each set.

If its #P-complete for 2-clauses per set at max ,then is the result also true for 1-clause per set at max?

Motivation behind this is to see how the number of solutions changes with respect to the overlap between clauses ,thus I want to know if its #p-complete even for 2-clauses per set ,this will make it easier to see the relation.

We know from this post that this variant is #P-complete where we can select at max only 3-clauses from each set mentioned above ,that's why I wanted to know if this is #P-complete where we allowed to select at max only 2 clauses from each set.

Is this variant of #Positive-2-SAT #P-complete?

Edit :

To clarify Steven confusion ,The sets are just a special way to classify the set of all possible positive-2-literal clauses with respect to k variables ,and my restriction is that we can make a set of 2-literal clauses as our input to the #Positive-2-SAT but we choose clauses from each set but we may not choose more than 3-clauses from any of these sets.

And any current answer doesn't resolve my question as they seem have to misunderstood the problem statement.

Answer 1

The question is ambiguous, as Steven has indicated.

One possible interpretation is that there is one set per variable, or in other words, each variable can occur in only two clauses. This is unlikely to be $\#\mathsf{P}$-complete, as indicated below.

Another possible intepretation is that there can be any number of sets, from 0 to the number of variables, and the sets are provided as part of the input, and the only restriction is that the formula must be consistent with the provided sets. In this case, the problem is $\#\mathsf{P}$-complete, as indicated below.

One set per variable

Assuming you have one set per variable, it can be solved in polynomial time.

Form an undirected graph with one vertex per variable and one edge per clause. Then there are at most two edges incident on each variable, i.e., each vertex has degree at most 2. This graph splits into a disjoint set of components, where each component is a simple cycle, a simple path, or an isolated vertice. For each component, you can count the number of satisfying assignments for that component (i.e., number of ways to assign values to the variables involved in that component) in polynomial time, then multiply them to get the total number of satisfying assignments for the original formula.

I leave it to you as a straightforward exercise describe a polynomial-time algorithm to count the number of satisfying assignments for an isolated vertex (hint: 2), for a simple path, and for a simple cycle. A simple path corresponds to a formula of the form

$$(x_1 \lor x_2) \land (x_2 \lor x_3) \land \dots \land (x_{k-1} \lor x_k),$$

and a simple cycle corresponds to a formula of the form

$$(x_1 \lor x_2) \land (x_2 \lor x_3) \land \dots \land (x_{k-1} \lor x_k) \land (x_k \lor x_1).$$

It is believed that $\mathsf{P} \ne \#\mathsf{P}$. Therefore, it is unlikely that this problem is $\#\mathsf{P}$-complete.

Any number of sets

In this case, one special case is where there are zero sets. This means that there are no restrictions on the formula, except that it must be a positive 2CNF formula.

It is known that counting the number of satisfying assignments to a positive 2CNF formula is $\#\mathsf{P}$-complete. If a special case of the problem is $\#\mathsf{P}$-hard, then the general problem must be $\#\mathsf{P}$-hard as well. It follows that your problem is $\#\mathsf{P}$-hard.

Also, it is easy to see that your problem is in $\#\mathsf{P}$.

It follows that your problem is $\#\mathsf{P}$-complete.