Please use this identifier to cite or link to this item:
https://research.matf.bg.ac.rs/handle/123456789/504
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Vujošević Janičić, Milena | en_US |
dc.contributor.author | Tomašević, Jelena | en_US |
dc.contributor.author | Janičić, Predrag | en_US |
dc.date.accessioned | 2022-08-13T10:14:41Z | - |
dc.date.available | 2022-08-13T10:14:41Z | - |
dc.date.issued | 2007-06-25 | - |
dc.identifier.issn | 0958695X | en |
dc.identifier.uri | https://research.matf.bg.ac.rs/handle/123456789/504 | - |
dc.description.abstract | 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. © J.UCS. | en |
dc.relation.ispartof | Journal of Universal Computer Science | en |
dc.subject | NP-complete problems | en |
dc.subject | Phase transition | en |
dc.subject | Prepositional satisfiability | en |
dc.subject | Random SAT problems | en |
dc.title | Random k-GD-SAT model and its phase transition | en_US |
dc.type | Article | en_US |
dc.identifier.doi | 10.3217/jucs-013-04-0572 | - |
dc.identifier.scopus | 2-s2.0-34250638309 | - |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/34250638309 | - |
dc.contributor.affiliation | Informatics and Computer Science | en_US |
dc.contributor.affiliation | Informatics and Computer Science | en_US |
dc.contributor.affiliation | Informatics and Computer Science | en_US |
dc.relation.firstpage | 572 | en |
dc.relation.lastpage | 591 | en |
dc.relation.volume | 13 | en |
dc.relation.issue | 4 | en |
item.fulltext | No Fulltext | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.cerifentitytype | Publications | - |
item.grantfulltext | none | - |
item.openairetype | Article | - |
crisitem.author.dept | Informatics and Computer Science | - |
crisitem.author.dept | Informatics and Computer Science | - |
crisitem.author.dept | Informatics and Computer Science | - |
crisitem.author.orcid | 0000-0001-5396-0644 | - |
crisitem.author.orcid | 0000-0002-9323-4695 | - |
crisitem.author.orcid | 0000-0001-8922-4948 | - |
Appears in Collections: | Research outputs |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.