On computing the size of a lattice and related decision problems (Q5959738)

A triple \(K=(G,M,I)\) is called a context if \(G\) and \(M\) are sets and \(I\subseteq G\times M\) is a relation. For a context \(K\) define a Galois connection for \(A\subseteq G\) and \(B\subseteq M\) such that \(A'=\{m\in M\); \(\exists g\in A\), \((g,m)\in I\}\) and \(B'=\{g\in G\); \(\exists m\in B\), \((g,m)\in I\}\). A pair \((A,B)\) where \(A\subseteq G\) and \(B\subseteq M\) is said to be a concept of a context \( K\) if \(B=A'\) and \(A=B'\). It is proved: a) the problem to find the number of all concepts of a given context is \#P-complete; b) the problem to decide whether for a given context \(K\) and a natural number \(k\) there exists a concept \((A,B)\) of \(K\) with \(|A|=k\) (or \(|B|=k\)) is NP-complete; c) there exists a polynomial time algorithm to decide whether for a given context \(K\) and a natural number \(k\) there exists a context \((A,B)\) of \(K\) with \(|A|\leq k\) (or \(|A|\geq k\), or \(|B|\leq k\) or \(|B|\geq k\)); d) the problem to decide whether for a given context \(K\) and a natural number \(k\) there exists a concept \((A,B)\) of \(K\) with \(|A|+|B|\leq k\) is NP-complete; e) there exists a polynomial time algorithm to decide whether for a given context \(K\) and a natural number \(k\) there exists a concept \((A,B)\) of \(K\) with \(|A|+|B|\geq k\).