On the Empirical Time Complexity of Scale-Free 3-SAT at the Phase Transition.
Thomas BläsiusTobias FriedrichAndrew M. SuttonPublished in: TACAS (1) (2019)
Keyphrases
- phase transition
- scale free
- small world networks
- satisfiability problem
- constraint satisfaction
- random sat
- sat problem
- complex networks
- hard problems
- easy hard easy pattern
- randomly generated
- small world
- np complete problems
- np complete
- scale free networks
- stochastic local search
- machine learning
- combinatorial problems
- power law
- graph coloring
- random instances
- computational complexity
- random constraint satisfaction problems
- decision problems
- cellular automata
- constraint satisfaction problems
- search space
- sat instances
- data mining
- social network analysis
- lower bound