NP-completeness of the set unification and matching problems. (English) Zbl 0643.68054

Automated deduction, Proc. 8th Int. Conf., Oxford/Engl. 1986, Lect. Notes Comput. Sci. 230, 489-495 (1986).
[For the entire collection see Zbl 0598.00015.]
The set-unification and set-matching problems, which are very restricted cases of the associative-commutative-idempotent unification and matching problems, respectively, are shown to be NP-complete. The NP-completeness of the subsumption check in first-order resolution follows from these results. It is also shown that commutative-idempotent matching and associative-idempotent matching are NP-hard, thus implying that the idempotency of a function does not help in reducing the complexity of matching and unification problems.


68Q25 Analysis of algorithms and problem complexity
68T99 Artificial intelligence