2
$\begingroup$

Suppose we have $n$ boolean variables, $x_1, \dots, x_n$. Some boolean variables can have implication relationships, e.g. $x_2 \implies x_5$, which means that if $x_2$ is true $x_5$ must also be true. There are no negations.

How do we efficiently count the number of distinct solutions?

I do have some ideas on how we can simplify the problem:

  1. If the implication graph is not connected we can compute the number of valid assignments for all disconnected parts independently and multiply their counts for the final result as they are completely independent.

  2. If there is a cycle in the implication graph we can replace all occurrences of all variables that participate in the cycle with a new single variable, as they must all be equal.

  3. We can remove all implications of the form $x_i \implies x_i$ as they are useless.

Repeating the above operations until fixed point occurs we are left with a bunch of connected directed acyclic graphs. But solving the problem efficiently for the DAG case still eludes me.

Improve this question
$\endgroup$
3
  • $\begingroup$ "There are no negations." I.e. despite $x_2\Rightarrow x_5$ there is no $\overline{x_5}\Rightarrow\overline{x_2}$ relation? This, of course, violates the standard rules of logic. $\endgroup$
    – rus9384
    Commented Jul 18 at 13:03
  • $\begingroup$ @rus9384 I just mean that the expression only has implications with positive variables $x_i$. $\neg x_i$ is not allowed in the expression. Of course I'm not saying the fundamental laws of logic are to be violated. $\endgroup$
    – orlp
    Commented Jul 18 at 14:48
  • $\begingroup$ Pretty sure #XOR-SAT is the only SAT variation that is not $\#P$-complete. $\endgroup$
    – rus9384
    Commented Jul 18 at 16:33

1 Answer 1

Reset to default
1
$\begingroup$

The problem is #P-complete, hence there is no polynomial-time solution (unless P = #P). This is proved in the following paper:

Hard Enumeration Problems in Geometry and Combinatorics. Nathan Linial. SIAM Journal on Algebraic Discrete Methods, volume 7, number 2, April 1986.

Related: Is #HORNSAT polynomial?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the reference. Does that imply it is hard to choose a valid assignment uniformly at random from the set of all valid assignments, or does there exist an effective algorithm for that regardless? What about an algorithm that allows $\pm \epsilon$ deviation from the true universal random probability any particular element is selected? $\endgroup$
    – orlp
    Commented Jul 18 at 8:00
  • $\begingroup$ @orlp, Good questions. I don't know. I think ability to sample approximately uniformly at random is connected to ability to approximately count the number of solutions, but I don't know the details, and I don't know the approximability of this problem. $\endgroup$
    – D.W. ♦
    Commented Jul 18 at 8:09

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.