The scaling window of the model \(d\)-\(k\)-CSP
type: Item
instance of: scholarly article
title: The scaling window of the model \(d\)-\(k\)-CSP
zbMATH Open document ID: 1334.82035
author: Guangyan Zhou
author: Jun Liu
author: Zongsheng Gao
published in: Journal of Mathematical Analysis and Applications
publication date: 2015-11-10T00:00:00Z
review text: A constraint satisfaction problem (CSP) consists of a set of \(n\) variables where each variable has its domain \(D\) (with size \(|D|=d\)); a set of \(t\) constraints where each constraint binds a subset of variables and has a list of legal tuples of values for these variables. In the paper the authors considered the model \(d-k\)-CSP and \(t=r\cdot {n\ln d\over -\ln p}\), where each constraint binds \(k\) distinct variables and permits \(pd^k\) tuples of values. It is proved that a phase transition of the model occurs at \(r_{\text{c}}=1\) and \(k\ln d= \alpha \ln n\), \(\alpha\in [{k\over 2k-1}+\varepsilon, 1]\), \(\varepsilon>0\) is a sufficiently small constant. The finite-size scaling upon the threshold of the model is determined. The second moment method is used.
reviewed by: U. A. Rozikov
Mathematics Subject Classification ID: 82B26
zbMATH DE Number: 6506803
zbMATH Keywords: constraint satisfaction problem
zbMATH Keywords: finite-size scaling
zbMATH Keywords: phase transition
zbMATH Keywords: the second moment method
MaRDI profile type: Publication
full work available at URL: j.jmaa.2015.09.015
OpenAlex ID: W1461974625
cites work: The phase transition in 1-in-\(k\) SAT and NAE 3-SAT
cites work: Random constraint satisfaction: A more accurate picture
cites work: The scaling window of the 2-SAT transition
cites work: Generalized satisfiability problems: Minimal elements and phase transitions.
cites work: A probabilistic analysis of randomly generated binary constraint satisfaction problems.
cites work: The 3-XORSAT threshold.
cites work: On the phase transitions of random \(k\)-constraint satisfaction problems
cites work: A general model and thresholds for random constraint satisfaction problems
cites work: A sharp threshold for a random constraint satisfaction problem
cites work: The satisfiability threshold for randomly generated binary constraint satisfaction problems
cites work: Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
cites work: Models for Random Constraint Satisfaction Problems
cites work: Constructing an asymptotic phase transition in random binary constraint satisfaction problems
cites work: Random constraint satisfaction: easy generation of hard (satisfiable) instances
cites work: Q4954175
cites work: Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
cites work: On the constraint length of random \(k\)-CSP
DOI: 10.1016/J.JMAA.2015.09.015
description: scientific article; zbMATH DE number 6506803