Introduction

One of the long-standing complexity problems in FCA is the problem of checking whether a given set of attributes is a pseudo-intent. In [4,5] it was proved that this problem lies in the class co-NP, however, the question whether the problem is complete in this class was still open. In [6] there was a conjecture that this problem is transhyp-hard [6], which would not mean that this problem is co-NPcomplete. In this paper we prove a stronger statement, namely that the problem is coNP-hard, which, together with the result from [4,5] means that the problem is coNP-complete. This main result has several consequences concerning essential intents and lectically largest pseudo-intent. Recognizing an essential intent is NP-complete and recognizing the lectically largest pseudo-intent is coNP-hard. The rest of the paper is organized as follows: In the second section we introduce the main definitions and give a precise problem statement. In the third section we give a proof of the main result. In the fourth section we discuss the complexity of some related problems, namely that of recognizing essential intents and generating pseudo-intents in the order dual to the lectic one.

Definitions

Let G and M be sets, called the set of objects and attributes, respectively. Let I be a relation I ⊆ G × M between objects and attributes: for g ∈ G, m ∈ M, gIm holds iff the object g has the attribute m. The triple K = (G, M, I) is called a (formal) context. If A ⊆ G, B ⊆ M are arbitrary subsets, then the Galois connection is given by the following derivation operators:

A ′ = {m ∈ M | gIm ∀g ∈ A} B ′ = {g ∈ G | gIm ∀m ∈ B}

The pair (A, B), where A ⊆ G, B ⊆ M , A ′ = B, and B ′ = A is called a (formal) concept (of the context K) with extent A and intent B (in this case we have also A ′′ = A and B ′′ = B). The set of attributes B is implied by the set of attributes A, or the implication A → B holds, if all objects from G that have all attributes from the set A also have all attributes from the set B, i.e. A ′ ⊆ B ′ .

The operation (•) ′′ is a closure operator [1], i.e. it is idempotent (X ′′′′ = X ′′ ), extensive (X ⊆ X ′′ ), and monotone (X

⊆ Y ⇒ X ′′ ⊆ Y ′′ ). Sets A ⊆ G, B ⊆ M are called closed if A ′′ = A and B ′′ = A.

Obviously, extents and intents are closed sets.

Implications obey the Armstrong rules:

A → A , A → B A ∪ C → B , A → B, B ∪ C → D A ∪ C → D .

A minimal (in the number of implications) subset of implications, from which all other implications of a context can be deduced by means of the Armstrong rules was characterized in [3]. This subset is called the Duquenne Guigues or stem base in the literature. The premises of the implications of the stem base can be given by pseudo-intents(see e.g. [1]): a set P ⊆ M is a pseudo-intent if P = P ′′ and Q ′′ ⊂ P for every pseudo-intent Q ⊂ P . For a closed set A ⊆ M such that P A the intersection A ∩ P is also closed (see [1]). A set

Q ⊆ M is called quasi-closed (quasi-intent) if for any R ⊆ Q one has R ′′ ⊆ Q or R ′′ = Q ′′ .

For example closed sets are quasi-closed. For a quasi-closed set

Q it holds that (Q ∩ C) ′′ = (Q ∩ C) for any closed set C such that Q C.

Another definition of a pseudo-intent, which we will use in this paper, is very close to that from [3]: a nonclosed set P ⊆ M is a pseudo-intent iff P is quasi-closed and Q ′′ ⊆ P for any quasi-closed set Q ⊂ P (see [4,5]). A set A ⊆ M is called an essential intent (essential-closed subset of attributes) iff there is a pseudo-intent P ⊆ M such that P ′′ = A.

Let G = {g 1 , . . . , g n } and M = {m 1 , . . . , m n } be sets with same cardinality. Then the context K = (G, M, I = ) is called contranominal scale, where I = = G × M \ {(g 1 , m 1 ), . . . , (g n , m n )}. The contranominal scale has the following property, which we will use later: for any H ⊆ M one has

H ′′ = H and H ′ = {g i | m i / ∈ H, 1 ≤ i ≤ n}.

Recognition of pseudo-intents

Here we discuss the algorithmic complexity of the problem of pseudo-intent recognition.

Problem: Pseudo-intent recognition (PI)

INPUT: A context K = (G, M, I

) and a set P ⊆ M . QUESTION: Is P a pseudo-intent of K?

In order to prove coN P -hardness of PI we consider the most well-known N P -complete problem, namely CNF satisfiability.

Problem: CNF satisfiability (SAT)INPUT: A boolean CNF formula f (x 1 , . . . , x n ) = C 1 ∧ . . . ∧ C k QUESTION: Is f satisfiable?

Consider an arbitrary CNF instance C 1 , . . . , C k with variables x 1 , . . . , x n , where

C i = (l i1 ∨. . .∨l ini ) (1 ≤ i ≤ k) are clauses and l ij ∈ {x 1 , . . . , x n }∪{¬x 1 , . . . , ¬x n } (1 ≤ i ≤ k, 1 ≤ j ≤ n i )

are some variables or their negations, called literals. From this instance we construct a context K = (G, M, I). Define

M = {p, C 1 , . . . , C k , x 1 , ¬x 1 , . . . , x n , ¬x n , e} G = {g x1 , g ¬x1 , . . . , g xn , g ¬xn , g CX , g C , g l1 , . . . , g ln } ∪ {g xj li | 1 ≤ i ≤ n, 1 ≤ j ≤ n} ∪ {g ¬xj li | 1 ≤ i ≤ n, 1 ≤ j ≤ n} For 1 ≤ i ≤ n define the set L i = {x 1 , ¬x 1 , . . . , x n , ¬x n } \ {x i , ¬x i }. In addition for 1 ≤ i ≤ n and 1 ≤ j ≤ n define the sets L xj i = L i \{x j } and L ¬xj i = L i \{¬x j }.

Now we are ready to define I. The relation I is given by two parts. The first part is

I ∩ {g x1 , g ¬x1 , . . . , g xn , g ¬xn } × M = C ∪ I = C = {(g xi , C j ) | x i / ∈ C j , 1 ≤ i ≤ n, 1 ≤ j ≤ k} ∪ {(g ¬xi , C j ) | ¬x i / ∈ C j , 1 ≤ i ≤ n, 1 ≤ j ≤ k} I = = {g x1 , g ¬x1 , . . . , g xn , g ¬xn } × {x 1 , ¬x 1 , . . . , x n , ¬x n } \ {(g x1 , x 1 ), (g ¬x1 , ¬x 1 ), . . . , (g xn , x n ), (g ¬xn , ¬x n )} , hence C ′ i ∩ {g x1 , g ¬x1 , .

. . , g xn , g ¬xn } is the set of objects which correspond to literals not included in C i (1 ≤ i ≤ k), and I = is the relation of the contranominal scale. The rest of I is given by the object intents

g ′ CX = M \ {p, e} g ′ C = {p} ∪ {C 1 , . . . , C k } g ′ li = {p} ∪ L i , 1 ≤ i ≤ n g xj li ′ = {p} ∪ L xj i , 1 ≤ i ≤ n, 1 ≤ j ≤ n g ¬xj li ′ = {p} ∪ L ¬xj i , 1 ≤ i ≤ n, 1 ≤ j ≤ n

Note that there are some objects (e.g. g l1 and g x1 l1 ) with the same intents, but this does not matter.

For any

A ⊆ {x 1 , ¬x 1 , . . . , x n , ¬x n } that satisfies A ∩ {x i , ¬x i } = ∅ for 1 ≤ i ≤ n, we define truth assignment φ A : φ A (x i ) =      true, if x i / ∈ A and ¬x i ∈ A; f alse, if ¬x i / ∈ A and x i ∈ A; f alse, otherwise (x i ∈ A and ¬x i ∈ A); p C1 C2 • • • C k x1 ¬x1 • • • xn ¬xn e gx 1 g¬x 1 . . . C I = gx n g¬x n gCX × • • • • • • × × • • • • • • • • • • • • × gC × × • • • • • • × g l 1 × L1 g x 1 l 1 × L x 1 1 g ¬x 1 l 1 × L ¬x 1 1 . . . . . . . . . g xn l 1 × L xn 1 g ¬xn l 1 × L ¬xn 1 . . . . . . . . . g ln × Ln g x 1 ln × L x 1 n g ¬x 1 ln × L ¬x 1 n . . . . . . . . . g xn ln × L xn n g ¬xn ln × L ¬xn n Table 1. Context K.

In the case x i / ∈ A and ¬x i / ∈ A for some 1 ≤ i ≤ n, φ A is undefined. Note that for A ⊆ {x 1 , ¬x 1 , . . . , x n , ¬x n } the truth assignment φ A is (correctly) defined iff A L i for every 1 ≤ i ≤ n.

Symmetrically for a truth assignment φ define the set

A φ = {¬x i | φ(x i ) = true} ∪ {x i | φ(x i ) = f alse}.

Before proving coN P -hardness of PI we prove some auxiliary statements. The following lemma is crucial for the reduction from SAT to the complement of PI.

Lemma 1 If a subset A ⊆ {x 1 , ¬x 1 , . . . , x n , ¬x n } is closed and A g ′ li for any 1 ≤ i ≤ n then φ A is defined and φ A satisfies f i.e f (φ A ) = true. Conversely, if a truth assignment φ satisfies f , then A φ is closed and A φ g ′ li for every 1 ≤ i ≤ n.

Proof. Let A ⊆ {x 1 , ¬x 1 , . . . , x n , ¬x n } and A is not a subset of any g ′ li (1 ≤ i ≤ n), then A L i for any 1 ≤ i ≤ n and hence (by definition of φ A ) φ A is defined. Since I = is the relation of contranominal scale and any intent can be expressed as the intersection of object intents, we have

A ′ = {g xi | x i / ∈ A} ∪ {g ¬xi | ¬x i / ∈ A}∪B, where B ⊆ G−{g x1 , g ¬x1 , . . . , g xn , g ¬xn }. Since A L i for any 1 ≤ i ≤ n we also have A L xj i and A L ¬xj i for every 1 ≤ i ≤ n and 1 ≤ j ≤ n. Thus B = {g CX }. Suppose A ′′ = A. Then A ∩ {C 1 , . . . , C k } = ∅ and hence for every 1 ≤ i ≤ k there is some g ∈ A ′ that C i / ∈ g ′ . Since C i ∈ g ′ CX and A ′ = {g xi | x i / ∈ A} ∪ {g ¬xi | ¬x i / ∈ A} ∪ {g CX } the latter means that g ∈ {g xi | x i / ∈ A} ∪ {g ¬xi | ¬x i / ∈ A}.

Then, by definition of the relation C, there is a literal x j / ∈ A or ¬x j / ∈ A that belongs to C i . Thus φ A satisfies C i for every 1 ≤ i ≤ k. Now let φ be a truth assignment and f (φ) = true. Obviously, A φ g ′ li for every 1 ≤ i ≤ n (by definition of A φ ). Then

A ′ φ = {g xi | x i / ∈ A φ } ∪ {g ¬xi | ¬x i / ∈ A φ } ∪ {g CX }. Note that A ′′ φ ∩ {x 1 , ¬x 1 , . . . , x n , ¬x n } = A φ ∩ {x 1 , ¬x 1 , . . . , x n , ¬x n } and A φ ⊆ g ′ CX . Hence A φ is closed iff A φ ∩{C 1 , . . . , C k } = ∅. Assume that C i ∈ A φ ∩ {C 1 , . . . , C k } for some 1 ≤ i ≤ k. This means that C i ∈ g ′

xj and C i ∈ g ′ ¬xr for every x j / ∈ A φ and ¬x r / ∈ A φ . But then by definition of the relation C the clause C i is not satisfied by φ.

2

Proposition 2 For any 1 ≤ i ≤ n if A ⊆ g ′ li then A is closed. Proof. Let A ⊆ g ′ li and p ∈ A. Then A ′′ = xj / ∈A g xj li ′ ∩ ¬xj / ∈A g ¬xj li ′ = A. In the case p / ∈ A we can express A ′′ as A ′′ = (A ∪ {p}) ′′ ∩ g ′ CX = A.2

Now we are ready to prove coN P -hardness of PI.

Theorem 3 PI is coN P -hard.

Proof. We reduce CNF to the complement of PI. Given a CNF instance f = C 1 ∧ . . . ∧ C k , we construct a context K like that described above (see Table 1). We take P = M \ {e} as a set for deciding whether it a pseudo-intent. Hence the corresponding PI instance is (K, P ) and we prove that f is satisfiable if and only if P is not a pseudo-intent of K. Without loss of generality we will assume that for every 1 ≤ i ≤ n the clause x i ∨ ¬x i is included in f (it does not affect satisfiability).

(⇒) Let f be satisfiable and let φ be the truth assignment that satisfies f (φ) = true. Consider the set Q = {p} ∪ A φ . As we will see later Q is a pseudointent, Q ⊂ P and Q ′′ = M P , and hence P is not a pseudo-intent. First let us check that Q ′′ = M . Since p ∈ Q we should test only that Q g ′ , where g ∈ {g C , g l1 , . . . , g ln } ∪ {g

xj li | 1 ≤ i ≤ n, 1 ≤ j ≤ n} ∪ {g ¬xj li | 1 ≤ i ≤ n, 1 ≤ j ≤ n}. Clearly Q g ′ C because A φ is not empty. By Lemma 1 for any 1 ≤ i ≤ n, A φ g ′ li , therefore Q g li . Hence Q g xj li ′ and Q g ¬xj li ′ (1 ≤ i ≤ n, 1 ≤ j ≤ n).

In order to prove that Q is a pseudo-intent we show that any proper subset of Q is closed. Consider an arbitrary set

A ⊂ Q. If p ∈ A then (since A = Q) there is a literal l ∈ {x 1 , ¬x 1 , . . . , x n , ¬x n } such that l ∈ Q and l / ∈ A. Thus by proposition 2 the subset A is closed. Now let p / ∈ A then if A = Q \ {p} = A φ by lemma 1 the subset A is closed. If A = Q \ {p} then A ⊂ A φ

and by proposition 2 the subset A is closed.

(⇐) Now let a pseudo-intent Q be a proper subset of P (i.e. Q ⊂ P ) and

Q ′′ P . Then Q is not a subset of any object intent of K. Together with the fact of quasi-closedness of Q this implies that Q∩g ′ is closed for any g ∈ G. Note that p ∈ Q since otherwise Q ⊆ g ′ CX . Consider Q ∩ g ′ C . Since Q ∩ g ′ C is closed and p ∈ Q ∩ g ′ C , there are only two possibilities: Q ∩ g ′ C = p or Q ∩ g ′ C = g ′ C . Assume Q ∩ g ′ C = g ′ C . Then Q = g ′ C ∪ B, where B ⊂ {x 1 , ¬x 1 , . . . , x n , ¬x n } and B = ∅ (because Q = P and Q = g ′ C ). Consider Q ∩ g ′ CX = {C 1 , . . . , C k } ∪ B. This set must be closed by quasi-closedness of Q. Note that {C 1 , . . . , C k } ∪ B g ′ li , for any 1 ≤ i ≤ n and {C 1 , . . . , C k } ∪ B g ′ C (since B = ∅). Thus (Q ∩ g ′ CX ) ′ ⊆ {g x1 , g ¬x1 , . . . , g xn , g ¬xn }. Since (Q ∩ g ′ CX ) ′ = ∅ there is a literal l ∈ {x 1 , ¬x 1 , . . . , x n , ¬x n } such that g l ∈ (Q ∩ g ′ CX ) ′ .

Then, by definition of g ′ l and the fact that some clause C i contains the literal l we get that

C i / ∈ Q ∩ g ′ CX . Thus Q ∩ g ′ C = p and Q \ {p} = Q ∩ g ′ CX ⊆ {x 1 , ¬x 1 , .

. . , x n , ¬x n }. Moreover, Q g ′ li for every 1 ≤ i ≤ n, hence φ = φ Q\{p} is (correctly) defined. Since Q \ {p} is closed by lemma 1, the truth assignment φ satisfies f .

2 In [4] it was shown that P I ∈ coNP hence we obtain Corollary 1. PI is coN P -complete.

Recognizing essential intents and lectically largest pseudo-intents

An important problem related to recognizing pseudo-intents is deciding whether a given set is the lectically largest pseudo-intent. Let M = {m 1 , . . . , m n } be a finite set with linear order on it (m Proof. We reduce SAT to the complement of LLPI as in the proof of Theorem 3 . The linear order on M is:

1 < • • • < m n ). For sets A ⊆ M and B ⊆ M we say that A lectically smaller than B (A < B, B is lectically larger than A) if ∃m i ∈ B \ A : A ∩ {m j ∈ M | j < i} = B ∩ {m j ∈ M | j < i}.p < C 1 < . . . < C k < x 1 < ¬x 1 < . . . < x n < ¬x n < e.

Since P = M \ {e} and M is closed, P is the lectically largest pseudo-intent iff P is a pseudo-intent.

2 Thus it is impossible to find the lectically largest pseudo-intent in polynomial time unless P = N P .

In [8] it was shown that pseudo-intents cannot be enumerated with polynomial delay in the lectic order (unless P = N P ). Proposition 4 shows that this also cannot be done in the dual order, i.e., the following corollary holds.

Corollary. Pseudo-intents cannot be generated with polynomial delay in the order dual to the lectic one unless P = N P .

Another problem related to the problem of recognizing pseudo-intents is that of recognizing essential intents. Proof. 1. NP-Hardness. We reduce SAT to EI, in the same way as in the reduction from SAT, to the complement of PI. Let us construct the context K 2 = (G, M \ {e}, I), where G, M and I are the sets of objects, attributes and the relation of context K from the proof of Theorem 3 (see Table 1). Obviously, M \ {e} is an essential intent of K 2 iff M \ {e} is not a pseudo-intent of K.

2. Membership in NP. The set A is an essential intent of the context K = (G, M, I) iff there is a pseudo-intent P ⊆ M such that P ′′ = A. Since a pseudointent is an inclusion-minimal quasi-closed set with the same closure (e.g. see [4]), a set A is an essential intent iff there is quasi-closed set Q ⊆ M such that Q ′′ = A. Quasi-closedness can be tested in polynomial time (see [4]). Hence a nondeterministic guess for checking essential-intent A can be a quasi-closed set Q such that Q ′′ = A.

2.

Conclusion

A long-standing complexity problem about the complexity of recognizing a pseudointent was solved. This problem was shown to be coNP-complete. This main result has several important consequences concerning essential intents and the lectically largest pseudo-intent. Recognizing an essential intent was shown to be NP-complete and recognizing the lectically largest pseudo-intent was shown to be coNP-hard. The latter fact means that pseudo-intents cannot be generated with polynomial delay in the order dual to the lectic one unless P = N P . Whether pseudo-intents cannot be generated with polynomial delay (unless P = N P ) in arbitrary order still remains an important open problem.