Random k-GD-Sat Model and its Phase Transition
| dc.creator | Vujošević-Janičić,Milena | |
| dc.creator | Tomašević,Jelena | |
| dc.creator | Janičić,Predrag | |
| dc.date | 2007 | |
| dc.date.accessioned | 2024-02-06T12:55:19Z | |
| dc.date.available | 2024-02-06T12:55:19Z | |
| dc.description | 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. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-013-04-0572 | |
| dc.identifier | https://lib.jucs.org/article/28778/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/9319 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 13(4): 572-591 | |
| dc.subject | propositional satisfiability | |
| dc.subject | random sat problems | |
| dc.subject | phase transition | |
| dc.subject | npcomplete problems | |
| dc.title | Random k-GD-Sat Model and its Phase Transition | |
| dc.type | Research Article |