On computing the size of a lattice and related decision problems (Q5959738): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1023/a:1013970520933 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W277700758 / rank | |||
Normal rank |
Latest revision as of 09:53, 30 July 2024
scientific article; zbMATH DE number 1726721
Language | Label | Description | Also known as |
---|---|---|---|
English | On computing the size of a lattice and related decision problems |
scientific article; zbMATH DE number 1726721 |
Statements
On computing the size of a lattice and related decision problems (English)
0 references
11 April 2002
0 references
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\).
0 references
context
0 references
concept lattice
0 references
complete problem
0 references
polynomial time algorithm
0 references
Galois connection
0 references