# Is solving the following system of boolean equations NP-hard?

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

• 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? Nov 16, 2020 at 3:42
• 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? Nov 16, 2020 at 16:03
• 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. Nov 16, 2020 at 16:08
• Sorry about the confusion! I just edited the question to make it clearer. Really appreciate all your help! Nov 16, 2020 at 17:55
• 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). Nov 16, 2020 at 17:58

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.
• 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. Nov 18, 2020 at 13:11