Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following expression $$ \bigvee_{i_1,\dots,i_N} \left(\bigwedge_{k=1}^N x_{i_k k} \right), $$ where the join operation is taken over all indices $(i_1,\dots,i_N) \in \{1,\dots,M \}^N$, so that it can be computed faster instead of looping through all multi-indices.

Apologies if this is a well-known problem (with or without solution). This is very much outside of my field of expertise, so I am hoping someone around here could give some feedback on it. Feel free to edit the tags as you see more appropriate.



It is equivalent to

$$\bigwedge_{k=1}^{N} \bigvee_{i_k=1}^{M} x_{i_k k}.$$

This is a much simpler expression: $NM$ terms instead of $M^N$ terms, if you expand everything out.


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.