<p>[Now that the question's been clarified I'll post my previous comment as an answer.]</p>
<p>It's in <span class="math-container">$\mathsf{P}$</span>. 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.</p>
<p>(If you want to <em>count</em> the number of solutions, on the other hand, that might be harder.)</p>

CC BY-SA 4.0
2020-11-18T13:11:48.503Z
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.
Geoffrey Irving
CC BY-SA 4.0
2020-11-18T16:41:39.493Z
@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!
Joshua Grochow
CC BY-SA 4.0
2020-11-16T22:57:25.827Z
2020-11-18T16:40:32.740Z
2020-11-18T16:40:32.740Z
Joshua Grochow
<p>I reduced a problem I'm currently working on to the following system of boolean equations:</p>
<p><span class="math-container">$$
X_i \iff
\begin{cases}
\bigvee_{B \in A_i} \bigwedge_{k \in B} X_k \\
true \\
false
\end{cases}
$$</span></p>
<p>Where <span class="math-container">$|B|&gt;=1$</span> for all <span class="math-container">$B \in A_i$</span> and each <span class="math-container">$X_i$</span> has exactly one of these defining equations.</p>
<p>I need to find <span class="math-container">$X_i$</span> that satisfies all these equations (<span class="math-container">$A_i$</span> are given). I'm wondering if this problem is NP-hard. I couldn't reduce the general boolean satisfiability problem to it yet.</p>
<p>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.</p>
<p>Thanks!</p>
<hr />
<p>Here's an example:
<span class="math-container">$$
X_1 \iff true \\
X_2 \iff false \\
X_3 \iff X_4 \\
X_4 \iff X_1 \vee (X_2 \wedge X_3)
$$</span></p>

CC BY-SA 4.0
2020-11-16T03:42:31.797Z
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?
Joshua Grochow
CC BY-SA 4.0
2020-11-16T14:45:33.450Z
Can negations not be expressed as follows? To obtain the negation of Xi, create variables Yi (this will be the negation), Ti, Fi. 
Require Fi <=> False, 
Ti <=> True, 
Fi <=> Xi AND Yi, 
Ti <=> Xi OR Yi. 

If this is indeed allowed in your type of set system, I will see if I can write an answer
user53923
CC BY-SA 4.0
2020-11-16T16:03:18.903Z
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?
Emil Jeřábek
CC BY-SA 4.0
2020-11-16T16:08:11.933Z
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.
Gamow
CC BY-SA 4.0
2020-11-16T16:26:53.880Z
They way it's written, I am reading the conditions as saying "each $X_i$ has to be either equivalent to (long formula), or it has to be true, or it has to be false", which is nonsense. What is actually meant by "... or $X_i = \mathrm{True}$ or $X_i = \mathrm{False}$"? Is that just noise that should be deleted?
Andrej Bauer
CC BY-SA 4.0
2020-11-16T17:55:40.897Z
Sorry about the confusion! I just edited the question to make it clearer. Really appreciate all your help!
lukas1994
CC BY-SA 4.0
2020-11-16T17:58:24.487Z
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).
lukas1994
<np-hardness><sat><reductions>
Is solving the following system of boolean equations NP-hard?
lukas1994
# Is solving the following system of boolean equations NP-hard?

(Asked by: username_0 on 2020-11-15)

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

**Tags:** np-hardness, sat, reductions

> **Comments:**
> **username_1**: 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?  
> **username_2**: Can negations not be expressed as follows? To obtain the negation of Xi, create variables Yi (this will be the negation), Ti, Fi.  Require Fi <=> False,  Ti <=> True,  Fi <=> Xi AND Yi,  Ti <=> Xi OR Yi.   If this is indeed allowed in your type of set system, I will see if I can write an answer  
> **username_3**: The disparity between username_1’s and username_2’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?  
> **username_4**: 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.  
> **username_5**: They way it's written, I am reading the conditions as saying "each $X_i$ has to be either equivalent to (long formula), or it has to be true, or it has to be false", which is nonsense. What is actually meant by "... or $X_i = \mathrm{True}$ or $X_i = \mathrm{False}$"? Is that just noise that should be deleted?  
> **username_0**: Sorry about the confusion! I just edited the question to make it clearer. Really appreciate all your help!  
> **username_0**: 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).  

---

## 1 answers

### Answer by username_1 on 2020-11-16. Score: 8 | Accepted answer

[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.)

> **Comments:**
> **username_6**: 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.  
> **username_1**: @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!  

---

