Computer Science – Artificial Intelligence
Scientific paper
2011-04-05
Computer Science
Artificial Intelligence
Scientific paper
Phase transitions in many complex combinational problems have been widely studied in the past decade. In this paper, we investigate phase transitions in the knowledge compilation empirically, where DFA, OBDD and d-DNNF are chosen as the target languages to compile random k-SAT instances. We perform intensive experiments to analyze the sizes of compilation results and draw the following conclusions: there exists an easy-hard-easy pattern in compilations; the peak point of sizes in the pattern is only related to the ratio of the number of clauses to that of variables when k is fixed, regardless of target languages; most sizes of compilation results increase exponentially with the number of variables growing, but there also exists a phase transition that separates a polynomial-increment region from the exponential-increment region; Moreover, we explain why the phase transition in compilations occurs by analyzing microstructures of DFAs, and conclude that a kind of solution interchangeability with more than 2 variables has a sharp transition near the peak point of the easy-hard-easy pattern, and thus it has a great impact on sizes of DFAs.
Gao Jian-Jian
Xu Ke
Yin Minghao
No associations
LandOfFree
Phase Transitions in Knowledge Compilation: an Experimental Study does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Phase Transitions in Knowledge Compilation: an Experimental Study, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Phase Transitions in Knowledge Compilation: an Experimental Study will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-321408