Extending semilattices is hard (Q793762)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Extending semilattices is hard |
scientific article; zbMATH DE number 3857176
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Extending semilattices is hard |
scientific article; zbMATH DE number 3857176 |
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
