归纳逻辑程序设计的扩张矩阵方法

摘要

归纳逻辑程序设计的核心问题是如何从背景知识中优选谓词构作满足约束的归纳假设。按Ｏｃｃａｍ准则，满足约束的最精简归纳假设为优，但迄今归纳逻辑程序设计中精简归纳假设构作的计算复杂性未明。该文基于扩张矩阵的方法证明精简归纳假设构作的计算复杂性是ＮＰ困难的，并给出构作优假设的启发式算法。