Random k-GD-Sat Model and its Phase Transition
Дата
Авторы
Vujošević-Janičić,Milena
Tomašević,Jelena
Janičić,Predrag
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
We present a new type of sat problem called the k-GD-SAT, which generalizes k-sat and GD-sat. In k-GD-SAT, clause lengths have geometric distribution, controlled by a probability parameter p; for p = 1, a k-GD-SAT problem is a k-SAT problem. We report on the phase transition between satisfiability and unsatisfiability for randomly generated instances of k-GD-SAT. We provide theoretical analysis and experimental results suggesting that there is an intriguing relationship (linear in the parameter 1/p) between crossover points for different parameters of k-GD-SAT. We also consider a relationship between crossover points for k-SAT and k-GD-SAT and provide links between these values.
Ключевые слова
propositional satisfiability , random sat problems , phase transition , npcomplete problems