On Different Models for Generating Random SAT Problems
P. Janicic ; N. Dedic ; G. Terzic
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
In the last decade a lot of effort has been invested into both theoretical and experimental analysis of sat phase transition. However, a deep theoretical understanding of this phenomenon is still lacking. Besides, many of experimental results are based on some assumptions that are not supported theoretically. In this paper we introduce the notion of sat--equivalence and we prove that some restrictions often used in sat experiments don't make an impact on location of a crossover point. We consider several fixed and random clause length sat models and relation between them. We also discuss one new sat model and report on a detected phase transition for it.
Publié le : 2012-01-26
Classification: 
@article{cai529,
     author = {P. Janicic and N. Dedic and G. Terzic},
     title = {On Different Models for Generating Random SAT Problems},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai529}
}
P. Janicic; N. Dedic; G. Terzic. On Different Models for Generating Random SAT Problems. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai529/