David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Minds and Machines 23 (1):95-103 (2013)
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|
References found in this work BETA
No references found.
Citations of this work BETA
Fenrong Liu & Kaile Su (2013). Logic and AI in China: An Introduction. [REVIEW] Minds and Machines 23 (1):1-4.
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.
Franz Dietrich & Christian List (2010). The Problem of Constrained Judgment Aggregation. In. In Thomas Uebel, Stephan Hartmann, Wenceslao Gonzalez, Marcel Weber, Dennis Dieks & Friedrich Stadler (eds.), The Present Situation in the Philosophy of Science. Springer. 125--139.
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 ( #224,108 of 1,089,157 )
Recent downloads (6 months)1 ( #69,735 of 1,089,157 )
How can I increase my downloads?