7
$\begingroup$

I reduced a problem I'm currently working on to the following system of boolean equations:

$$ X_i \iff \begin{cases} \bigvee_{B \in A_i} \bigwedge_{k \in B} X_k \\ true \\ false \end{cases} $$

Where $|B|>=1$ for all $B \in A_i$ and each $X_i$ has exactly one of these defining equations.

I need to find $X_i$ that satisfies all these equations ($A_i$ are given). I'm wondering if this problem is NP-hard. I couldn't reduce the general boolean satisfiability problem to it yet.

Ideally, I would find an algorithm to solve this problem in polynomial time. If it's NP-hard I guess I have to hope that SAT solvers can solve it reasonably fast.

Thanks!


Here's an example: $$ X_1 \iff true \\ X_2 \iff false \\ X_3 \iff X_4 \\ X_4 \iff X_1 \vee (X_2 \wedge X_3) $$

$\endgroup$
7
  • 5
    $\begingroup$ After unit propagation what's left will be monotone, so if it's not visibly unsatisfiable, then the all-true assignment always satisfies it. Or did you mean to allow negations in some places too? $\endgroup$ Nov 16 '20 at 3:42
  • 3
    $\begingroup$ The disparity between Joshua Grochow’s and user53923’s comments highlights another ambiguity in the question: for each $i$, does the system include only one equation with left-hand side $X_i$, or can there be more of them? $\endgroup$ Nov 16 '20 at 16:03
  • 3
    $\begingroup$ With $x\lor y \iff\text{True}$ and $x\land y \iff\text{False}$, you get $x$ as the negation of $y$. This allows you to construct an arbitrary set of clauses over Boolean variables, so that the problem is as hard as SAT. $\endgroup$
    – Gamow
    Nov 16 '20 at 16:08
  • 1
    $\begingroup$ Sorry about the confusion! I just edited the question to make it clearer. Really appreciate all your help! $\endgroup$
    – lukas1994
    Nov 16 '20 at 17:55
  • 2
    $\begingroup$ I actually think @JoshuaGrochow's solution should work (input all the false values to see which variables have to be false and then set everything else to true). $\endgroup$
    – lukas1994
    Nov 16 '20 at 17:58
8
$\begingroup$

[Now that the question's been clarified I'll post my previous comment as an answer.]

It's in $\mathsf{P}$. Start with unit propagation. Afterwards, what's left on the right-hand sides will be monotone, so will be satisfied by setting all remaining variables to True.

(If you want to count the number of solutions, on the other hand, that might be harder.)

$\endgroup$
2
  • 1
    $\begingroup$ How is something like $X \iff Y$ monotone? If $X$ is false, doesn't it force $Y$ to be false? I agree that the all true assignment works, but this doesn't seem the same as monotonicity. $\endgroup$ Nov 18 '20 at 13:11
  • 1
    $\begingroup$ @GeoffreyIrving: You're right, I should've been more specific that it's what's on the right-hand sides that is monotone, and therefore the all true assignment works. (But the point is, to find a satisfying assignment here one doesn't need full monotonicity.) I updated my answer to reflect this. Thanks! $\endgroup$ Nov 18 '20 at 16:41

Your Answer

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

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