scientific article; zbMATH DE number 4049047

From MaRDI portal
Publication:3785940





[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.




Cited in
(31)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3785940)