Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Assume you are given a matrix $$ X= \begin{bmatrix} x_1^1 & x_1^2 & \dots & x_1^m \\ x_2^1 & x_2^2 & \dots & x_2^m \\ \vdots & \vdots & \ddots & \vdots \\ x_n^1 & x_n^2 & \dots & x_n^m \end{bmatrix} $$ such that all $x_i^j \in \big\{0,1\big\}$, $\vee$ is the logical OR, and: $$ \forall i,j, \quad x_{i}^j = \begin{cases} x_{i+1}^{j}\vee x_{i+1}^{j-1} & \text{if }\:j\neq1,\\ x_{i+1}^1\vee x_{i}^m & \text{otherwise}. \end{cases} $$ This is quite similar to the Pascal triangle with binomials, except here we are dealing with $0/1$ variables and regular addition is replaced by the logical OR.

The problem now is to minimize: $$S=\sum_{i,j} x_i^j,$$ where the trivial case $S=0$ with all $x_i^j=0$ is not an option. The sum is the one in the integers: $0<S\leq n m$.

EDIT: What can we say about the case where the $\vee$ operator is no longer the logical OR, but is defined by: $0\vee0=0$, $1\vee0=0\vee1=1$ and $1\vee1\in\{0,1\}$.

Does this problem reduces to another one? Maybe there are references that I am not aware of.

Thanks for your help.

share|improve this question
How is $x_i^j$ defined for $i=n$? And: is it really $x_i^m$ in the second of the definition? –  Marcus Ritt Mar 2 '12 at 10:36
When $i=n$, there is no constraint: values are free to choose. And yes, it is $x_i^m$: there is this linking property the Pascal triangle does not have. –  wwjoze Mar 4 '12 at 11:48
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.