Phase Transitions in Knowledge Compilation: an Experimental Study
  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.
