Ordering \(D\)-classes and computing Schein rank is hard (Q1186845)

The author proves that deciding whether a principal ideal in the semigroup of all binary relations on a finite set contains another principal ideal is \(NP\)-complete. The proof shows that determining the Schein rank of a binary matrix is not likely to be solved by an efficient algorithm (the Schein rank of a binary matrix \(A\) is the minimal number of binary matrices, each of them corresponding to a rectangular binary relation whose Boolean sum equals \(A\)).