Phase Transitions for Scale-Free SAT Formulas.
Tobias FriedrichAnton KrohmerRalf RothenbergerAndrew M. SuttonPublished in: AAAI (2017)
Keyphrases
- phase transition
- scale free
- random sat
- small world networks
- sat problem
- satisfiability problem
- complex networks
- small world
- constraint satisfaction
- scale free networks
- np complete
- cnf formula
- power law
- randomly generated
- random constraint satisfaction problems
- hard problems
- stochastic local search
- graph coloring
- combinatorial problems
- propositional formulas
- conjunctive normal form
- small world properties
- sat instances
- np complete problems
- community structure
- propositional satisfiability
- max sat
- random instances
- boolean satisfiability
- cellular automata
- social networks
- random graphs
- davis putnam
- biological networks