SCIRP Mobile Website
Paper Submission

Why Us? >>

  • - Open Access
  • - Peer-reviewed
  • - Rapid publication
  • - Lifetime hosting
  • - Free indexing service
  • - Free promotion service
  • - More citations
  • - Search engine friendly

Free SCIRP Newsletters>>

Add your e-mail address to receive free newsletters from SCIRP.

 

Contact Us >>

Article citations

More>>

Monasson, R., Zecchina, R., Kirkpatrick, S., et al. (1996) Phase Transition and Search Cost in the (2 + p)-SAT Problem. Proceedings of the 4th Workshop on Physics and Computation, Boston, 229-232.

has been cited by the following article:

  • TITLE: Complexity Analysis of Mixed Constraint Satisfaction Problems

    AUTHORS: Xiaomei Shi

    KEYWORDS: Model RBmix, Tree-Like Resolution, Complexity, Hard Instances

    JOURNAL NAME: Open Journal of Applied Sciences, Vol.7 No.4, April 26, 2017

    ABSTRACT: This paper analyzes the resolution complexity of a random CSP model named model RBmix, the instance of which is composed by constraints with different length. For model RBmix, the existence of phase transitions has been established and the threshold points have been located exactly. By encoding the random instances into CNF formulas, it is proved that almost all instances of model RBmix have no tree-like resolution proofs of less than exponential size. Thus the model RBmix can generate abundant hard instances in the threshold. This result is of great significance for algorithm testing and complexity analysis in NP-complete problems.