%0 Journal Article %1 kuznetsov/ord/2001 %A Kuznetsov, Sergei %D 2001 %I Springer Netherlands %J Order %K 2017 complexity concepts fca kde lattice seminar %N 4 %P 313-321 %R 10.1023/A:1013970520933 %T On Computing the Size of a Lattice and Related Decision Problems %U http://dx.doi.org/10.1023/A:1013970520933 %V 18 %X 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.

@article{kuznetsov/ord/2001, 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.}, added-at = {2017-08-14T11:13:06.000+0200}, author = {Kuznetsov, Sergei}, biburl = {https://www.bibsonomy.org/bibtex/234a2c5ebb906f3e787f716ea3d77d8c3/johirth}, description = {SpringerLink - Order, Volume 18, Number 4}, doi = {10.1023/A:1013970520933}, interhash = {919f81b52542d9dd6783623499511bb8}, intrahash = {34a2c5ebb906f3e787f716ea3d77d8c3}, issn = {0167-8094}, journal = {Order}, keyword = {Mathematics and Statistics}, keywords = {2017 complexity concepts fca kde lattice seminar}, number = 4, pages = {313-321}, publisher = {Springer Netherlands}, timestamp = {2017-08-14T11:13:06.000+0200}, title = {On Computing the Size of a Lattice and Related Decision Problems}, url = {http://dx.doi.org/10.1023/A:1013970520933}, volume = 18, year = 2001 }