多項式時間仮説推論を達成するネットワーク化バブル伝播法の述語論理への拡張

概要

論文の詳細を見る
A hypothetical reasoning is a useful knowledge-processing framework applicable to system diagnosis, design, etc. Hewever, due to its non-monotonic inference nature, it takes exponential computation time to find a solution hypothesis set to prove a given goal. As for its propositional-logic version, we have shown previously that a polynomial-time approximate solution method of O-1 integer programming, Pivot and Complement method, can be effectively employed by transforming the hypothetical reasoning problem into a O-1 integer programming. Also, a networked-bubble-propagation (NBP) method constructed by reforming this approximate method into a networked mechanism has been presented to achieve an even faster inference. In this paper, we extend the NBP method to deal with predicate-logic hypothetical reasoning with variable expression but function-free. Furthermore, the network used for the inference (short term memory in this paper) stays within a reasonable size, since it is extended in a stepwise manner iff the current network has insufficient element hypotheses and rules to prove the given goal. With this extended NBP method, it is shown that a polynomial-time hypothetical reasoning can be achieved against the number of possible element hypotheses even in the case of predicate-logic knowledge.
1995-09-01