Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT.
Tobias FriedrichAnton KrohmerRalf RothenbergerThomas SauerwaldAndrew M. SuttonPublished in: CoRR (2017)
Keyphrases
- power law
- random sat
- phase transition
- satisfiability problem
- sat problem
- random constraint satisfaction problems
- small world
- scale free
- np complete
- lower bound
- long range correlations
- constraint satisfaction problems
- random sat instances
- max sat
- search algorithm
- stochastic local search
- temporal logic
- sat instances
- davis putnam
- upper bound
- computational complexity
- propositional satisfiability
- power law distribution
- propositional logic