Portal de Periódicos da CAPES

PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS

2010; World Scientific; Volume: 21; Issue: 06 Linguagem: Inglês

10.1142/s012905411000774x

1793-6373

Junping Zhou, Ping Huang, Minghao Yin, Chunguang Zhou,

Model-Driven Software Engineering Techniques

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.