• Threshold properties of random...

Treffer: Threshold properties of random boolean constraint satisfaction problems

Title:
Threshold properties of random boolean constraint satisfaction problems
Authors:
ISTRATE, Gabriel
Source:
Typical case complexity and phase transitionsDiscrete applied mathematics. 153(1-3):141-152
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2005.
Publication Year:
2005
Physical Description:
print, 13 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Théorie programmation, Programming theory, Calcul automatique, Computing, Cálculo automático, Condition existence, Existence condition, Condición existencia, Condition suffisante, Sufficient condition, Condición suficiente, Informatique théorique, Computer theory, Informática teórica, Modèle probabiliste, Probabilistic model, Modelo probabilista, Problème satisfiabilité, Satisfiability problem, Problema satisfactibilidad, Seuil, Threshold, Umbral, Transition phase, Phase transitions, Transición fase, CSP, Problème aléatoire, Random problem, Problème satisfaction contrainte, Random constraint satisfaction problems, Sharp thresholds
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
CCS-5, Basic and Applied Simulation Science, Los Alamos National Laboratory, Mail Stop M 997, Los Alamos, NM 87545, United States
ISSN:
0166-218X
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=17350531
Rights:
Copyright 2006 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.17350531
Database:
PASCAL Archive

Weitere Informationen

We study threshold properties of random constraint satisfaction problems under a probabilistic model due to Molloy [Models for random constraint satisfaction problems, in: Proceedings of the 32nd ACM Symposium on Theory of Computing, 2002]. We give a sufficient condition for the existence of a sharp threshold. In the boolean case, it gives an independent proof for the more difficult half of a classification result conjectured by Creignou and Daudé [Generalized satisfiability problems: minimal elements and phase transitions. Theor. Comput. Sci. 302(1-3) (2003)417-430], proved in a restricted case by the same authors [Combinatorial sharpness criterion and phase transition classification for random CSPs, Inform. Comput. 190(2) (2004) 220-238], and established by them [Coarse and sharp thresholds for random generalized satisfiability problems, in: M. Drmota, P. Flajolet, D. Gardy, B. Gittenberger (Eds.), Mathematics and Computer Science III: Algorithms, Trees, Combinatorics and Probabilities, Birkhauser, Basel, September 2004, pp. 507-517] while this paper was in the refereeing process.