Scale-Free Random SAT Instances
Open Access
- 20 June 2022
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 15 (6) , 219
Abstract
We focus on the random generation of SAT instances that have properties similar to real-world instances. It is known that many industrial instances, even with a great number of variables, can be solved by a clever solver in a reasonable amount of time. This is not possible, in general, with classical randomly generated instances. We provide a different generation model of SAT instances, called scale-free random SAT instances. This is based on the use of a non-uniform probability distribution to select variable i, where is a parameter of the model. This results in formulas where the number of occurrences k of variables follows a power-law distribution , where . This property has been observed in most real-world SAT instances. For , our model extends classical random SAT instances. We prove the existence of a SAT–UNSAT phase transition phenomenon for scale-free random 2-SAT instances with when the clause/variable ratio is . We also prove that scale-free random k-SAT instances are unsatisfiable with a high probability when the number of clauses exceeds . The proof of this result suggests that, when , the unsatisfiability of most formulas may be due to small cores of clauses. Finally, we show how this model will allow us to generate random instances similar to industrial instances, of interest for testing purposes.
Keywords
All Related Versions
Funding Information
- MCIN/AEI/10.13039/501100011033 (PID2019-109137GB-C21)
This publication has 38 references indexed in Scilit:
- Random 2-SAT with Prescribed Literal DegreesAlgorithmica, 2007
- The state of SATDiscrete Applied Mathematics, 2007
- Structural properties of scale‐free networks2002
- Universal Behavior of Load Distribution in Scale-Free NetworksPhysical Review Letters, 2001
- The scaling window of the 2‐SAT transitionRandom Structures & Algorithms, 2001
- Resilience of the Internet to Random BreakdownsPhysical Review Letters, 2000
- 2+p-SAT: Relation of typical-case complexity to the nature of the phase transitionRandom Structures & Algorithms, 1999
- A critical point for random graphs with a given degree sequenceRandom Structures & Algorithms, 1995
- The evolution of random graphsTransactions of the American Mathematical Society, 1984
- Random GraphsThe Annals of Mathematical Statistics, 1959