Minds and Machines 23 (1):95-103 (2013)
AbstractModel 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
Similar books and articles
Finite Model Theory and its Applications.Erich Grädel, Phokion Kolaitis, Libkin G., Marx Leonid, Spencer Maarten, Vardi Joel, Y. Moshe, Yde Venema & Scott Weinstein - 2007 - Springer.
The Equivalence of NF-Style Set Theories with "Tangled" Theories; the Construction of Ω-Models of Predicative NF (and More).M. Randall Holmes - 1995 - Journal of Symbolic Logic 60 (1):178-190.
Beauty in Science: A New Model of the Role of Aesthetic Evaluations in Science. [REVIEW]Ulianov Montano - 2013 - European Journal for Philosophy of Science 3 (2):133-156.
Sensorimotor Process with Constraint Satisfaction. Grounding of Meaning (EUCogII 2009).Christophe Menant - manuscript
Model‐Based Reasoning in Distributed Cognitive Systems.Nancy J. Nersessian - 2006 - Philosophy of Science 73 (5):699-709.
The Consistency Strength of an Infinitary Ramsey Property.George Kafkoulis - 1994 - Journal of Symbolic Logic 59 (4):1158-1195.
On the Decision Problem for Two-Variable First-Order Logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
Strong Paraconsistency and the Basic Constructive Logic for an Even Weaker Sense of Consistency.Gemma Robles & José M. Méndez - 2009 - Journal of Logic, Language and Information 18 (3):357-402.
Added to PP
Historical graph of downloads
References found in this work
Consistency in Networks of Relations.Alan K. Mackworth - 1977 - Artificial Intelligence 8 (1):99-118.
Random Constraint Satisfaction: Easy Generation of Hard (Satisfiable) Instances.Ke Xu, Frédéric Boussemart, Fred Hemery & Christophe Lecoutre - 2007 - Artificial Intelligence 171 (8-9):514-534.
Local Search with Edge Weighting and Configuration Checking Heuristics for Minimum Vertex Cover.Shaowei Cai, Kaile Su & Abdul Sattar - 2011 - Artificial Intelligence 175 (9-10):1672-1696.
On the Phase Transitions of Random K-Constraint Satisfaction Problems.Yun Fan & Jing Shen - 2011 - Artificial Intelligence 175 (3-4):914-927.