×

Phase transitions of EXPSPACE-complete problems. (English) Zbl 1215.68162

Summary: 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 – the CONFORMANT PLAN-NONEXISTENCE algorithm and the 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 is not greater than \(\theta _{\text{ub}}\), the CONFORMANT PLAN-NONEXISTENCE algorithm can prove that nearly all the conformant planning instances have no solution. If the number of the operators is not lower than \(\theta _{\text{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.

MSC:

68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1016/0004-3702(95)00045-3 · doi:10.1016/0004-3702(95)00045-3
[2] Remi Monasson, Nature 400 pp 133–
[3] DOI: 10.1090/S0894-0347-99-00305-7 · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7
[4] Frieze A., Journal of Algorithms 53 pp 469– · Zbl 0729.68029
[5] DOI: 10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U · Zbl 0936.68038 · doi:10.1002/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U
[6] DOI: 10.1016/S0004-3702(96)00030-6 · Zbl 0907.68177 · doi:10.1016/S0004-3702(96)00030-6
[7] Xu Ke, Journal of Artificial Intelligence Research 12 pp 93–
[8] DOI: 10.1002/rsa.20015 · Zbl 1077.68118 · doi:10.1002/rsa.20015
[9] Bryce D., Journal of Artificial Intelligence Research 26 pp 35–
[10] Helmert M., Journal of Artificial Intelligence Research 26 pp 191– · JFM 01.0389.02
[11] DOI: 10.1016/j.artint.2008.11.012 · Zbl 1191.68636 · doi:10.1016/j.artint.2008.11.012
[12] Junping Zhou, Journal of Software 20 pp 290– · doi:10.3724/SP.J.1001.2009.00290
[13] Cormen T. H., Introduction to Algorithms (1990) · Zbl 1158.68538
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.