Super solutions of the model RB

References

[1] Xu K , Li W . Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 2000, 12 : 93– 103

[2] Smith B M , Dyer M E . Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence, 1996, 81( 1−2): 155– 181

[3] Xu K , Li W . Many hard examples in exact phase transitions. Theoretical Computer Science, 2006, 355( 3): 291– 302

[4] Zhao C , Zhang P , Zhang Z , Xu K . Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains. Physical Review E, 2012, 85( 1): 016106–

[5] Zhao C , Zhou H , Zheng Z , Xu K . A message-passing approach to random constraint satisfaction problems with growing domains. Journal of Statistical Mechanics: Theory and Experiment, 2011, 2011(02) : P02019–

[6] Xu W , Zhang P , Liu T , Gong F . The solution space structure of random constraint satisfaction problems with growing domains. Journal of Statistical Mechanics: Theory and Experiment, 2015, 2015(12) : P12006–

[7] Hebrard E, Hnich B, Walsh T. Super solutions in constraint programming. In: Proceedings of the 1st International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming. 2004, 157– 172

[8] Zhang P , Gao Y . A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming. Theoretical Computer Science, 2017, 657 : 98– 110

[9] Wang B , Zhou G . Super solutions of random (3+p)-SAT. Theoretical Computer Science, 2019, 793 : 14– 27

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant Nos. 61702019, 11801028).

RIGHTS & PERMISSIONS

2022 Higher Education Press