On Computing the Size of a Lattice and Related Decision Problems
Order, 18 (4):
313-321 (2001)DOI: 10.1023/A:1013970520933
Abstract
The problem of determining the size of a finite concept lattice is shown to be #P-complete. Since any finite lattice can be represented as a concept lattice, the problem of determining the size of a lattice given by the ordered sets of its irreducibles is also #P-complete. Some results about NP-completeness or polynomial tractability of decision problems related to concepts with bounded extent, intent, and the sum of both are given. These problems can be reformulated as decision problems about lattice elements generated by a certain amount of irreducibles.
Description
SpringerLink - Order, Volume 18, Number 4
