0
$\begingroup$

#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.

$\endgroup$
22
  • 1
    $\begingroup$ Sounds like a very weird restriction on the inputs. What's the motivation? $\endgroup$
    – Dmitry
    Jun 13, 2023 at 16:05
  • $\begingroup$ 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 we its #p-complete even for 2-clauses per set ,this will make it easier to see the relation. $\endgroup$
    – Anuj
    Jun 13, 2023 at 16:09
  • $\begingroup$ Well, somewhat. It's not clear to me how this restriction bounds "overlap between clauses", since some elements can still appear a linear number of times. $\endgroup$
    – Dmitry
    Jun 14, 2023 at 4:00
  • $\begingroup$ this restriction makes it easier for me to reason about overlappings between clauses $\endgroup$
    – Anuj
    Jun 14, 2023 at 6:50
  • 1
    $\begingroup$ It makes no sense for the set $S$ of allowable literals to be part of the input of your problem along with the 2-SAT formula $\phi$. Once you are given $\phi$, $S$ plays no role (or, if you wish, you can find a valid $S$ for any $\phi$). If $S$ is a parameter of the problem then it's unclear what you're asking: each instantiation of the problem only admits a finite number of input formulas $\phi$ and can be solved in constant time. Can you define your problem precisely? What is part of the input and what is part of the problem? A formal definition of the set of input instances would help. $\endgroup$
    – Steven
    Jun 23, 2023 at 17:42

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Sorry for being a bit pedantic, but $\mathsf{P}$ is a class of decision problems, and the problem described is not a decision problem (therefore cannot be in $\mathsf{P}$. $\endgroup$
    – Nathaniel
    Jun 23, 2023 at 19:40
  • $\begingroup$ "Where each component is a simple cycle, a simple path, or an isolated vertice" - I don't see why. In the example from the statement, it's possible to have clauses $ae,be,ce,de$, which means that $e$ has $4$ neighbors. $\endgroup$
    – Dmitry
    Jun 23, 2023 at 19:52
  • $\begingroup$ @Dmitry, good point! I misunderstood the problem statement. On looking again, I think the problem statement is ambiguous. See my revised answer. Hopefully this addresses your feedback now. $\endgroup$
    – D.W.
    Jun 23, 2023 at 20:00
  • $\begingroup$ @Nathaniel, thank you! I've revised my answer to correct this mistake. $\endgroup$
    – D.W.
    Jun 23, 2023 at 20:00
  • $\begingroup$ @D.W It seems you've misunderstood the problem statement ,I've edited the post to explain the confusion ,if its still not clear ,let me know. $\endgroup$
    – Anuj
    Jun 24, 2023 at 11:44

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.