Extending semilattices is hard (Q793762)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Extending semilattices is hard |
scientific article |
Statements
Extending semilattices is hard (English)
0 references
1983
0 references
The author shows that a general solution for the Arbib-Manes problem of finding an extension with the minimal number of join irreducibles of a finite composite algebra would yield a solution of the set basis problem by giving a set basis of smallest cardinality. This problem is known to be NP-complete and hence is intrinsically hard.
0 references
NP-complete problems
0 references
extension
0 references
join irreducibles
0 references
finite composite algebra
0 references
