1. PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS.
- Author
-
ZHOU, JUNPING, HUANG, PING, YIN, MINGHAO, ZHOU, CHUNGUANG, and Cai, Jin-Yi
- Subjects
PHASE transitions ,PROBLEM solving ,ALGORITHMS ,MATHEMATICAL proofs ,ARTIFICIAL intelligence ,CONSTRAINT satisfaction ,EMPIRICAL research - Abstract
This paper explores the phase transitions of the EXPSPACE-complete problems, which mainly focus on the conformant planning problems. The research presents two conformant planning algorithms-CONFORMANT PLAN-NONEXISTENCE algorithm and CONFORMANT PLAN-EXISTENCE algorithm. By analyzing the features of the two algorithms, the phase transition area of the conformant planning problems is obtained. If the number of the operators isn't greater than θ
ub , the CONFORMANT PLAN-NONEXISTENCE algorithm can prove that nearly all the conformant planning instances have no solution. If the number of the operators isn't lower than θlb , the CONFORMANT PLAN-EXISTENCE algorithm can prove that nearly all the conformant planning instances have solutions. The results of the experiments show that there exist phase transitions from a region where almost all the conformant planning instances have no solution to a region where almost all the conformant planning instances have solutions. [ABSTRACT FROM AUTHOR]- Published
- 2010
- Full Text
- View/download PDF