Minds and Machines 23 (1):95-103 (2013)
|Abstract||Model RB is a model of random constraint satisfaction problems, which exhibits exact satisfiability phase transition and many hard instances, both experimentally and theoretically. Benchmarks based on Model RB have been successfully used by various international algorithm competitions and many research papers. In a previous work, Xu and Li defined two notions called i-constraint assignment tuple and flawed i-constraint assignment tuple to show an exponential resolution complexity of Model RB. These two notions are similar to some kind of consistency in constraint satisfaction problems, but seem different from all kinds of consistency so far known in literatures. In this paper, we explicitly define this kind of consistency, called variable-centered consistency, and show an upper bound on a parameter in Model RB, such that up to this bound the typical instances of Model RB are variable-centered consistent|
|Keywords||Constraint satisfaction problems Model RB Consistency|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Heike Mildenberger & Saharon Shelah (2002). The Relative Consistency of G < Cf(Sym(Ω)). Journal of Symbolic Logic 67 (1):297 - 314.
Erich Grädel, Phokion Kolaitis, Libkin G., Marx Leonid, Spencer Maarten, Vardi Joel, Y. Moshe, Yde Venema & Scott Weinstein (2007). Finite Model Theory and its Applications. Springer.
M. Randall Holmes (1995). The Equivalence of NF-Style Set Theories with "Tangled" Theories; the Construction of Ω-Models of Predicative NF (and More). Journal of Symbolic Logic 60 (1):178-190.
Ulianov Montano (2013). Beauty in Science: A New Model of the Role of Aesthetic Evaluations in Science. [REVIEW] European Journal for Philosophy of Science 3 (2):133-156.
Tzuchien Tho (2008). The Consistency of Inconsistency. Symposium 12 (2):70-92.
Nancy J. Nersessian (2006). Model-Based Reasoning in Distributed Cognitive Systems. Philosophy of Science 73 (5):699-709.
Paolo Liberatore (2007). Consistency Defaults. Studia Logica 86 (1):89 - 110.
George Kafkoulis (1994). The Consistency Strength of an Infinitary Ramsey Property. Journal of Symbolic Logic 59 (4):1158-1195.
Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi (1997). On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic 3 (1):53-69.
Gemma Robles & José M. Méndez (2009). Strong Paraconsistency and the Basic Constructive Logic for an Even Weaker Sense of Consistency. Journal of Logic, Language and Information 18 (3):357-402.
Added to index2012-02-15
Total downloads3 ( #213,351 of 722,863 )
Recent downloads (6 months)1 ( #60,917 of 722,863 )
How can I increase my downloads?