部分蕴涵复杂性分析

Complexity Analysis of Partial Implication Semantics

极小模型和部分蕴涵语义在人工智能很多领域中有着广泛的应用.本文分析当前件和后件分别是文字、文字集和公式时,极小模型和部分蕴涵语义的复杂性问题并做相关讨论.结果表明,随着前件和后件越复杂,相关的判定问题复杂度越高.而这些判定问题的复杂度都在多项式谱系的前两层之内.

Minimal model and partial implication semantics play important roles in the sub-fields of artificial intelligence. In this paper, the complexity issues of minimal model and partial implication semantics are analyzed when the antecedent and the consequent are literals, literal sets and formulas respectively. The results show that the complexities of minimal model and partial implication semantics increase when the antecedent and consequent become more complex. Moreover, the complexities of all these decision problems lie in the first two layers of polynomial hierarchy.