Huang, Ping (Northeast Normal University) | Yin, Minghao (Northeast Normal University) | Xu, Ke (Beijing University of Aeronautics and Astronautics)

The study of phase transition phenomenon of NP complete problems plays an important role in understanding the nature of hard problems. In this paper, we follow this line of research by considering the problem of counting solutions of Constraint Satisfaction Problems (#CSP). We consider the random model, i.e. RB model. We prove that phase transition of #CSP does exist as the number of variables approaches infinity and the critical values where phase transitions occur are precisely located. Preliminary experimental results also show that the critical point coincides with the theoretical derivation. Moreover, we propose an approximate algorithm to estimate the expectation value of the solutions number of a given CSP instance of RB model.

The random k-SAT model is extensively used to compare satisfiability algorithms or to find the best settings for the parameters of some algorithm. Conclusions are derived from the performances measured on a large number of random instances. The size of these instances is, in general, small to get these experiments done in reasonable time. This assumes that the small size formulas have the same properties as the larger ones. We show that small size formulas have at least a characteristic that makes them relatively easier than the larger ones (beyond the increase in the size of the formulas).

Giráldez-Cru, Jesús (IIIA-CSIC) | Levy, Jordi (IIIA-CSIC)

Nowadays, many industrial SAT instances can be solved efficiently by modern SAT solvers. However, the number of real-world instances is finite. Therefore, the process of development and test of SAT solving techniques can benefit of new models of random formulas that capture more realistically the features of real-world problems. In many works, the structure of industrial instances has been analyzed representing them as graphs and studying some of their properties, like modularity. In this paper, we use modularity, or community structure, to define a new model of pseudo-industrial random SAT instances, called Community Attachment. We prove that the phase transition point, if exists, is independent on the modularity. We evaluate the adequacy of this model to real industrial problems in terms of SAT solvers performance, and show that modern solvers do actually exploit this community structure.

Ian P. Gent and Toby Walsh * Department of Computer Science University of Strathclyde Glasgow G1 1XL United Kingdom ipg@cs, strath, ac.uk, twOcs, strath, ac.uk Abstract We show that phase transition behavior similar to that observed in NPcomplete problems like random 3-SAT occurs further up the polynomial hierarchy in problems like random 2-QSAT. The differences between QSAT and SAT in phase transition behavior that Cadoli et al report are largely due to the presence of trivially unsatisfiable problems. Once they are removed, we see behavior more familiar from SAT and other NPcomplete domains. There are, however, some differences. Problems with short clauses show a large gap between worst case behavior and median, and the easy-hard-easy pattern is restricted to higher percentiles of search cost. We compute the "constralnedness" of k-QSAT problems for any k, and use this to predict the location of phase transitions.