
## Conclusions

Our work concerns the phase transition in knowledge compilation of k-SAT, which is accompanied with an easy-hard-easy pattern on the space rather than the runtimes. We first conjectured that the ratios of clauses to variables in the random SAT model have great impact on the sizes of compilation results, where an easy-hard-easy pattern exists similar with many phase transition phenomena. DFAs, OBDDs and d-DNNFs, which are commonly employed to compile real-world problems off-line, have been chosen as the target languages for compilation. Experimental results on randomly generated k-SAT have been demonstrated in a number of figures, by which the conjecture has been supported. Interestingly, we suggested curves of average sizes using different target languages have peak points with the same value of r when k is fixed. It can also be concluded that the sizes for 3-SAT increase exponentially as n grows when r>0.3, whereas the sizes increase polynomially when r<0.3. Hence, there exists another phase transition that separates the regions of polynomial and exponential sizes. Furthermore, we try to explain the reason that the existence of the easy-hard-easy pattern. From approximate analyses on the structures of DFAs, we concluded that paths with more than one adjoint edge have great impact on the sizes of DFAs, and these paths imply a kind of solution interchangeability in the SAT instances. As can be seen that those paths has strong relation with implicants, further works will include uncovering more inherent relations between them. Acknowledgements. We would like to thank Nina Narodytska for her BDD compiler. The work described in this paper was supported by the National Natural Science Foundation of China Granted No. 60803102 and 60973033. 

## References

1. Cheeseman P., Kanefsky B., Taylor W. M.: Where the Really Hard Problems Are. In: proc. 

IJCAI'91, pp. 331--340. Morgan Kaufmann Publishers, Inc. (1991) 
2. Xu K., Li W.: Exact Phase Transitions in Random Constraint Satisfaction Problems. J. Artif. Intell. 

Res. 12, 93--103 (2000) 
3. Achlioptas D., Naor A., Peres Y.: Rigorous location of phase transitions in hard optimization problems. Nature 435, 759--764 (2005) 
4. Slaney J., Walsh T.: Phase Transition Behavior: from Decision to Optimization, In: proc. SAT'02, 
(2002) 
5. Gent I. P., Walsh T.: Beyond NP: the QSAT phase transition. In: proc. AAAI/IAAI'99, pp. 

648--653. AAAI Press (1999) 
6. Creignou N., Daudé H., Egly U., Rossignol R.: New Results on the Phase Transition for Random Quantified Boolean Formulas. In: proc. SAT'08, LNCS, vol. 4996, pp.34--47. Springer, Heidelberg (2008) 
7. Rintanen J: Phase Transitions in Classical Planning: An Experimental Study. In proc. ICAPS'04, pp. 

101--110 (2004) 
8. Zhou J., Huang P., Yin M.: Zhou C.: Phase Transitions of EXPSPACE-Complete Problems. Int. J. 

Found. Comput. Sci. 21, 1073--1088 (2010) 