The Complexity of Counting Problems in Equational Matching

AbstractWe introduce a class of counting problems that arise naturally in equational matching and investigate their computational complexity. If E is an equational theory, then #E-Matching is the problem of counting the number of most general E-matchers of two given terms. #E-Matching is a well-defined algorithmic problem for every finitary equational theory. Moreover, it captures more accurately the computational difficulties associated with finding minimal complete sets of E-matchers than the corresponding decision problem for E-matching does.In 1979, L. Valiant developed a computational model for measuring the complexity of counting problems and demonstrated the existence of #P-complete problems, i.e., counting problems that are complete for counting non-deterministic Turing machines of polynomial-time complexity. Using the theory of #P-completeness, we analyze the computational complexity of #E-matching for several important equational theories E. We establish that if E is one of the equational theories A, C, AC, I, U, ACI, Set, ACU, or ACIU, then #E-Matching is a #P-complete problem. We also show that there are equational theories, such as the restriction of AC-matching to linear terms, for which the underlying decision matching problem is solvable in polynomial time, while the associated counting matching problem is #P-complete