Ordering \(D\)-classes and computing Schein rank is hard (Q1186845)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ordering \(D\)-classes and computing Schein rank is hard |
scientific article |
Statements
Ordering \(D\)-classes and computing Schein rank is hard (English)
0 references
28 June 1992
0 references
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\)).
0 references
semigroup of binary relations
0 references
principal ideal
0 references
NP-complete
0 references
Schein rank
0 references
binary matrix
0 references
rectangular binary relation
0 references
Boolean sum
0 references