# Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data
## 3 Computational Complexity Results
By assumption, at least one literal of each clause must be true, and so for each \(p^{k}\in P\) at least one of the symbols \(s_{i}\) corresponding to 0, 1 positions of \(p^{k}\) must be different from \(p^{k}_{i}\), due to the particular construction of \(p^{k}\)It follows that \(s\) cannot be in \(S(p^{k})\) for all \(k\) and so \(s\) cannot be in \(S(P)\). In a similar way, given a string \(s\) not in \(S(P)\) we can reverse the previous reasoning and obtain a satisfying truth assignment for the SAT instance. To see that PATTERN INCOMPLETENESS is also in NP it suffices to observe that verifying that a string \(s\
otin S(P)\) does not belong to \(S(P)\) takes polynomial time, as previously described. Since PATTERN INCOMPLETENESS and PATTERN COMPLETENESS are complements of each other, we have:  
**Corollary 1**: _PATTERN COMPLETENESS is co-NP-complete._  
**Proposition 4**: _PATTERN EQUIVALENCE is co-NP-complete._  
We transform PATTERN COMPLETENESS into PATTERN EQUIVALENCE. Given a set \(P\) of patterns, instance of PATTERN COMPLETENESS, the corresponding instance of PATTERN EQUIVALENCE consists of the set \(P\) plus a set \(Q\) containing only the pattern \((\dashrightarrow\dashrightarrow)\) (which generates \(\{0,1\}^{n}\)). For a no-instance, there exists a string \(s\in S(P)\) and \(s\
otin S(Q)\), or vice versa, and this \(s\) is a short certificate. **Proposition 5**: _PATTERN EQUIVALENCE MINIMALITY is co-NP-hard._  
We describe a transformation from PATTERN COMPLETENESS. Given an instance of PATTERN COMPLETENESS we define a corresponding instance of PATTERN EQUIVALENCE MINIMALITY by choosing \(K=1\). Without loss of generality, we may assume that for each \(i\), the values \(p_{i}\)'s across all \(p\in P\) are not all identical (since, otherwise, we may discard each position where all symbols are equal and reduce the instance to an equivalent one). At this point, the only pattern that can be equivalent to \(P\) is \((\dashrightarrow\dashrightarrow)\). Since PATTERN COVER MINIMALITY is a particular case of PATTERN EQUIVALENCE MINIMALITY we have by Proposition 2:  
**Proposition 6**: _PATTERN EQUIVALENCE MINIMALITY is NP-hard._  
By Propositions 5 and 6, PATTERN EQUIVALENCE MINIMALITY is both NP-hard and co-NP-hard. To date it is not known whether the classes of NP-complete problems and co-NP-complete problems coincide or are disjoint. The widely believed conjecture is that they are disjoint. Following this conjecture we conclude that it is unlikely that PATTERN EQUIVALENCE MINIMALITY is in NP or in co-NP, and so we expect its complexity to be beyond the classes NP and co-NP. It is obvious that, given a set \(P\) of patterns, generating \(S(P)\) takes exponential time in general for the mere fact that \(|S(P)|\) can be of exponential size. It is perhaps surprising that the reverse, i.e., given a set of strings \(S\), generating \(P(S)\) is polynomial. Indeed it turns out that \(P(S)\) is of polynomial size and also the algorithm that generates \(P(S)\) is polynomial. We devote the next section to this issue.