Portal de Periódicos da CAPES

PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP

2012; World Scientific; Volume: 23; Issue: 01 Linguagem: Inglês

10.1142/s0129054112500025

1793-6373

Junping Zhou, Minghao Yin, Xiangtao Li, Wang Jinyan,

Constraint Satisfaction and Optimization

This paper further explores the phase transitions of the EXPSPACE-complete problems, focusing on the conformant plan modification. By analyzing features of the conformant plan modification, quantitative results are obtained. If the number of actions is't greater than θ ub , almost all the conformant planning instances can't be solved with the conformant plan modification. If the number of actions is't lower than θ lb , almost all the conformant planning instances can be solved with the conformant plan modification. The results of the experiments show that there indeed exists an experimental threshold γ c of density (ratio of number of actions to number of propositions), which separates the region where almost all conformant planning instances can't be solved with the conformant plan modification from the region where almost all conformant planning instances can be solved with the conformant plan modification.