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

A POLYNOMIAL ALGORITHM FOR AN ABDUCTION PROBLEM

作　　者：张宏[1] 马绍汉[1] 

机构地区：[1]山东大学计算机系

出　　处：《计算机研究与发展》1995年第6期21-28,45,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金

摘　　要：在实际生活中经常会遇到利用已知的一些事实来解释观察到的现象问题，其推理方法可分为演绎、诱导和归纳。在已知的事实中往往会有矛盾的知识存在，利用这些含有矛盾的已知事实来解释数据的问题，在诱导推理中称之为矛盾诱导问题。Ｂｙｌａｎｄｅｒ［２］在其文章中已经证明了该类问题为ＮＰ完全的。本文提出一类２ＳＡＴ诱导问题，证明该类问题属于Ｐ类，并对其进行扩展，得出了关于矛盾诱导问题的最大Ｐ问题及最小ＮＰ完全问题。In this paper, we offer one kind of incompatibility abduction problems──2SAT abduction problem, and prove it is tractable(P). Meanwhile, it is extended to obtain the maximum tractable problem and the minimum NP-complete problem of incompatibility abduction problems.

关 键 词：诱导问题 多项式 时间算法 逻辑推理 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]