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) $$

Improve this question
$\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$
    – Joshua Grochow
    Commented Nov 16, 2020 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$
    – Emil Jeřábek
    Commented Nov 16, 2020 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
    Commented Nov 16, 2020 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
    Commented Nov 16, 2020 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
    Commented Nov 16, 2020 at 17:58

1 Answer 1

Reset to default
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.)

Improve this answer
$\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$
    – Geoffrey Irving
    Commented Nov 18, 2020 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$
    – Joshua Grochow
    Commented Nov 18, 2020 at 16:41

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.