Phase Transition and Network Structure in Realistic SAT Problems.
Soumya C. KambhampatiThomas LiuPublished in: AAAI (2013)
Keyphrases
- network structure
- phase transition
- sat problem
- satisfiability problem
- constraint satisfaction
- social networks
- randomly generated
- complex networks
- boolean satisfiability
- np complete
- combinatorial problems
- np complete problems
- sat instances
- propositional satisfiability
- davis putnam
- random sat
- hard problems
- network size
- graph coloring
- stochastic local search
- max sat
- link prediction
- small world
- cellular automata
- random instances
- random constraint satisfaction problems
- upper bound
- search algorithm
- clustering coefficient
- social network analysis
- constraint satisfaction problems
- dynamic programming
- reinforcement learning