Phase Transition of Tractability in Constraint Satisfaction and Bayesian Network Inference

Yong Gao

There has been great interest in identifying tractable subclasses of NP complete problems and designing efficient algorithms for these tractable classes. Constraint satisfaction an…