Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT.
Tobias FriedrichAnton KrohmerRalf RothenbergerThomas SauerwaldAndrew M. SuttonPublished in: ESA (2017)
Keyphrases
- power law
- random sat
- phase transition
- satisfiability problem
- sat problem
- small world
- random constraint satisfaction problems
- random sat instances
- upper bound
- random graphs
- np complete
- max sat
- scale free
- sat instances
- stochastic local search
- long range correlations
- lower bound
- degree distribution
- clustering coefficient
- orders of magnitude
- randomly generated
- propositional logic
- sat solvers
- boolean satisfiability
- power law distribution