Phase Transitions in Knowledge Compilation: An Experimental Study

Abstract Phase transitions, as a kind of well-known phenomena in artificial intelligence, have attracted a great amount of attention in recent years [1, 2]. Many NP-complete problems, such as random SAT and random Constraint Satisfaction Problems (CSPs), have a critical point that separates overconstrained and underconstrained regions, and soluble-to-insoluble phase transition occurs at this critical point, which is always accompanied with the transitions of CPU runtimes. Both systematic search algorithms and local search algorithms suffer an easy-hard-easy pattern when solving those problems.

Authors

• Jian Gao 0007
• Minghao Yin
• Ke Xu 0001

Keywords

No keywords are indexed for this paper.