The scaling window of the model \(d\)-\(k\)-CSP (Q890505): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q1928133 |
||
Property / author | |||
Property / author: Zong Sheng Gao / rank | |||
Revision as of 16:27, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The scaling window of the model \(d\)-\(k\)-CSP |
scientific article |
Statements
The scaling window of the model \(d\)-\(k\)-CSP (English)
0 references
10 November 2015
0 references
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.
0 references
constraint satisfaction problem
0 references
finite-size scaling
0 references
phase transition
0 references
the second moment method
0 references