No label defined (Q3740274)

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 3974342
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3974342

      Statements

      0 references
      1986
      0 references
      complexity of unification
      0 references
      logic programming
      0 references
      intelligent backtracking
      0 references
      NP-complete problems
      0 references
      PROLOG
      0 references
      [For the entire collection see Zbl 0587.00020.] This paper investigates the computational complexity question for intelligent backtracking based on finding either all or particular maximal unifiable or minimal nonunifiable subsets of constraints. The following results are stated and proved: the 0-X-1 unifiable subset, the largest maximal unifiable subset, the bounded unifiability, and the bounded resolution unifiability problem are NP-complete, respectively. Corresponding results on minimal nonunifiability are also NP-complete problems. All these problems have relevance to the design of improved backtracking in theorem provers and PROLOG implementations using standard or non- standard unification. These results explain why heuristic and approximate strategies are necessary in (semi-) intelligent backtracking. Average time complexity should also be interesting to be analyzed.
      0 references

      Identifiers