No label defined (Q3785940)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4049047
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4049047

      Statements

      0 references
      0 references
      1986
      0 references
      set-unification
      0 references
      set-matching
      0 references
      NP-complete
      0 references
      [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.
      0 references

      Identifiers