制約充足問題の多項式時間全解探索について

概要

論文の詳細を見る
Many AI tasks can be formulated as constraint satisfaction problems (CSP). Since CSP is NP-complete, it is expected that there are no effective algorithms for solving every CSP. So it is important to find out some simpler subclasses of CSP which can be solved in polynomial time. The paper proposes a new breadth-first algorithm for finding all solutions of a given CSP, and analyzes its complexity. According to the algorithm, a new hierarchy of subclasses of CSP computable in polynomial time, which we call k-bounded, is introduced. It is conjectured that determining the value k of a given CSP is NP-hard. By giving a concrete algorithm, however, it is proved that, when k is fixed to a constant, the computational complexity of deciding whether a CSP is k-bounded or not is O(n^<k+1>) in the best case, and O(n!) in the worst case. Some properties of k-bounded and k-tree are also clarified.
社団法人人工知能学会の論文
1994-09-01