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
1986
0 references
complexity of unification
0 references
logic programming
0 references
intelligent backtracking
0 references
NP-complete problems
0 references
PROLOG
0 references
0.9239376187324524
0 references
0.8000966310501099
0 references
0.7727414965629578
0 references
0.7651568055152893
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