论文标题
凸几何含义基础的复杂性结果
Complexity Results for Implication Bases of Convex Geometries
论文作者
论文摘要
凸几何形状是满足反交换性质的有限零关闭系统。使用含义碱基给出了与凸几何形式相关的两个开放问题的复杂性结果。特别是，通过确定从最小基数生成器问题的一般闭合系统来减少，优化凸几何的含义基础的问题被证明是NP-HARD。此外，即使是决定含义基础是否定义凸几何形状的问题也被证明是通过从布尔重言术问题中的减少来确定的。
A convex geometry is finite zero-closed closure system that satisfies the anti-exchange property. Complexity results are given for two open problems related to representations of convex geometries using implication bases. In particular, the problem of optimizing an implication basis for a convex geometry is shown to be NP-hard by establishing a reduction from the minimum cardinality generator problem for general closure systems. Furthermore, even the problem of deciding whether an implication basis defines a convex geometry is shown to be co-NP-complete by a reduction from the Boolean tautology problem.
