On the complexity of enumerating pseudo-intents

被引：38

作者：

Distel, Felix ^{[2
]}

Sertkaya, Baris ^{[1
]}

机构：

[1] SAP Res Ctr Dresden, D-01187 Dresden, Germany

[2] Tech Univ Dresden, D-01187 Dresden, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2011年 / 159卷 / 06期

关键词：

Formal concept analysis; Implications; Duquenne-Guigues Base; Pseudo-intents; Complexity; MONOTONE DUALIZATION; HARDNESS;

D O I：

10.1016/j.dam.2010.12.004

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We investigate whether the pseudo-intents of a given formal context can efficiently be enumerated. We show that they cannot be enumerated in a specified lexicographic order with polynomial delay unless P = NP. Furthermore we show that if the restriction on the order of enumeration is removed, then the problem becomes at least as hard as enumerating minimal transversals of a given hypergraph. We introduce the notion of minimal pseudo-intents and show that recognizing minimal pseudo-intents is polynomial. Despite their less complicated nature, surprisingly it turns out that minimal pseudo-intents cannot be enumerated in output-polynomial time unless P = NP. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：450 / 466

页数：17