scientific article; zbMATH DE number 3974342

From MaRDI portal
Publication:3740274





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











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 Q3740274)