# Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data
## 3 Computational Complexity Results  
The previous definitions lead to the following decision problems [12]:  
1. PATTERN COVER: given a set \(S\) of strings and a set \(P\) of patterns, is \(P\) a cover of \(S\), i.e., \(S=S(P)\)? 2. PATTERN COVER MINIMALITY: given a set \(S\) of strings and a constant \(K\), does there exist a cover \(P\) of \(S\) such that \(\left|P\right|\leq K\)? 3. PATTERN EQUIVALENCE: given two sets \(P\), \(Q\) of patterns, are they equivalent, i.e., \(S(P)=S(Q)\)? 4. PATTERN EQUIVALENCE MINIMALITY: given a set \(P\) of patterns and a constant \(K<\left|P\right|\), does there exist an equivalent set of patterns \(Q\) such that \(\left|Q\right|\leq K2\)
5. PATTERN COMPLETENESS: given a set \(P\) of patterns, is it complete, i.e., \(S(P)=\left\{0,1\right\}^{n}\)? 6. PATTERN INCOMPLETENESS: given a set \(P\) of patterns, is it not complete, i.e., does there exist a string \(s\in\left\{0,1\right\}^{n}\) such that \(s\
otin S(P)\)? We first note that, given a set \(P\) of patterns and a string \(s\in\left\{0,1\right\}^{n}\), determining whether \(s\in S(P)\) or \(s\
otin S(P)\) is polynomial. Indeed, given a pattern \(p\) and a string \(s\) we may check in time \(O(n)\) whether \(s\) can be generated by \(p\) or not. Hence, given a set \(P\) of patterns we have to repeat the check for each \(p\in P\). If the check is false for each \(p\in P\) we have \(s\
otin S(P)\), otherwise we have \(s\in S(P)\). Proposition 1: _PATTERN COVER is polynomial._  
Proof. : For each \(s\in S\) we check whether \(s\in S(P)\) or not. Hence in time \(O(n\left|S\right|\left|P\right|)\) we may decide whether \(S\subseteq S(P)\) or not. In order to decide whether \(S(P)\subseteq S\) or not, for each pattern \(p\in P\) we count the number \(n(p)\) of strings in \(S\) compatible for \(p\). Let \(k\) be the number of gaps in \(p\). Then \(p\) is compatible for \(S\), i.e., \(S(p)\subseteq S\), if and only if \(n(p)=2^{k}\). Computing \(n(p)\) can be done in time \(O(n\left|S\right|)\). Overall, checking whether \(S(P)\subseteq S\) takes \(O(n\left|S\right|\left|P\right|)\) time. Proposition 2: _PATTERN COVER MINIMALITY is NP-complete._  
Proof. : We observe that PATTERN COVER MINIMALITY is basically the same as MINIMALITY INORMAL FORM (see [17] p. 261), which we repeat here for the sake of completeness: Given a set \(U=\left\{u_{1},u_{2},\ldots,u_{n}\right\}\) of variables, a set \(A\subseteq\left\{T,F\right\}^{n}\) of \"truth assignments\", and an integer \(K>0\), does there exist a disjunctive normal form expression \(E\) over \(U\), having no more than \(K\) disjuncts, which is true for precisely the assignments in \(A\) and no others? We show the equivalence of the two problems by the following map which builds a PATTERN COVER MINIMALITY instance. Each element \(a\in A\) becomes an input binary string (with 0 representing false, and 1 representing true), while each disjunct \(d\) is mapped into a pattern \(p\) such that \(p_{i}=1\) if \(u_{i}\) appears in \(d\), \(p_{i}=0\) if \(\
eg u_{i}\) appears in \(d\) and a \(p_{i}=\) - otherwise. Proposition 3: _PATTERN INCOMPLETENESS is NP-complete._  
Proof. : We reduce SAT to PATTERN INCOMPLETENESS. Given a SAT instance with \(n\) literals and \(m\) clauses we derive a set \(P\) of \(m\) patterns \(p^{k}\), \(k=1,\ldots,m\), (each pattern associated to each clause), as follows: for each variable \(i\) and each clause \(k\), if the literal \(x_{i}\) is present in the clause, we set \(p^{k}_{i}=0\), if the literal \(\
eg x_{i}\) is present in the clause, we set \(p^{k}_{i}=1\), and if neither \(x_{i}\) nor \(\
eg x_{i}\) are present in the clause, we set \(p^{k}_{i}=\) - (note that the pattern values \(p^{k}_{i}\in\left\{0,1\right\}\) are set opposite to the truth values of the literals \(x_{i}\)). Assume SAT is satisfiable and let \(x\) be a satisfying truth assignment. Define a string \(s\) as \(s_{i}=1\) if \(x_{i}=\) TRUE and \(s_{i}=0\) if \(x_{i}=\) FALSE.