On Different Models for Generating Random SAT Problems
Abstract
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.Downloads
Download data is not yet available.
Published
2012-02-21
How to Cite
Janicic, P., Dedic, N., & Terzic, G. (2012). On Different Models for Generating Random SAT Problems. Computing and Informatics, 20(5), 451–469. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/529
Issue
Section
Articles