一类赋权诱导问题的多项式时间算法

A POLYNOMIAL ALGORITHM FOR WEIGHTED ABDUCTION PROBLEM

本文介绍了赋权诱导推理的基本概念及其求解算法复杂性研究的现状．诱导推理在人工智能领域有广泛的应用前景，但现有的求解算法都未能从根本上排除ＮＰ－难解性的困扰，本文考虑了其中一类子问题：二阶独立赋权诱导问题，并给出求其最优解的多项式时间算法．本文还对其它诱导问题进行了分析，给出Ｐ问题与ＮＰ问题的分界线．

This paper gives basic concept of weighted abduction problems and the outline of current complexity results to solve it. Abduction problems are widely used in the area of AI,but the present methods do not get rid of the difficulties of NP-hardness. This paper gives a polynomial algorithm to find the best explanation of a subclass problem of weighted abduction problems, second order independent abduction problem, and proved that solving second order independent incompatibility abduction is NP-complete. Some other P and NP-hardness weighted abduction problems are also given.