Some Complexity Results about Essential Closed Sets

Abstract. We examine the enumeration problem for essential closed sets of a formal context. Essential closed sets are sets that can be writ-ten as the closure of a pseudo-intent. The results for enumeration of essential closed sets are similar to existing results for pseudo-intents, al-beit some differences exist. For example, while it is possible to compute the lectically first pseudo-intent in polynomial time, we show that it is not possible to compute the lectically first essential closed set in poly-nomial time unless P = NP. This also proves that essential closed sets cannot be enumerated in the lectic order with polynomial delay unless P = NP. We also look at minimal essential closed sets and show that they cannot be enumerated in output polynomial time unless P = NP.