Phase Transition and Network Structure in Realistic SAT Problems
Soumya C. KambhampatiThomas LiuPublished in: CoRR (2013)
Keyphrases
- network structure
- phase transition
- sat problem
- satisfiability problem
- constraint satisfaction
- np complete
- social networks
- max sat
- randomly generated
- boolean satisfiability
- link prediction
- network size
- complex networks
- stochastic local search
- davis putnam
- combinatorial problems
- sat instances
- propositional satisfiability
- hard problems
- graph coloring
- small world
- np complete problems
- cellular automata
- random constraint satisfaction problems
- random instances
- random graphs
- constraint satisfaction problems
- np hard
- optimal solution
- random sat
- bayesian networks