Complexity of matching problems (Q1099615)

The associative-commutative matching problem is shown to be NP-complete; more precisely, the matching problem for terms in which some function symbols are uninterpreted and others are both associative and commutative, is NP-complete. It turns out that the similar problems of associative-matching and commutative-matching are also NP-complete. However, if every variable appears at most once in a term being matched, then the associative-commutative matching problem is shown to have an upper-bound of \(O(| s| *| t|^ 3)\), where \(| s|\) and \(| t|\) are, respectively, the sizes of the pattern s and the subject t.