Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/524
Title: GD-SAT model and crossover line
Authors: Janičić, Predrag 
Affiliations: Informatics and Computer Science 
Keywords: NP completeness;Phase transition;SAT problem
Issue Date: 1-Jan-2001
Journal: Journal of Experimental and Theoretical Artificial Intelligence
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. It is still a very challenging problem to determine a relationship between crossover points for different SAT problems. This paper introduces one new class of randomly generated SAT problems, GD-SAT, and we experimentally show there is a phase transition for the problems in this class. On the basis of both analytical and experimental arguments we conjecture that there is a surprisingly simple, linear relationship between crossover points for problems in this class. This relationship is of both theoretical and practical importance.
URI: https://research.matf.bg.ac.rs/handle/123456789/524
ISSN: 0952813X
DOI: 10.1080/09528130110063083
Appears in Collections:Research outputs

Show full item record

SCOPUSTM   
Citations

2
checked on Dec 20, 2024

Page view(s)

6
checked on Dec 24, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.