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

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