The phase transition in random regular exact cover (Q329450)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The phase transition in random regular exact cover |
scientific article |
Statements
The phase transition in random regular exact cover (English)
0 references
21 October 2016
0 references
Summary: A \(k\)-uniform, \(d\)-regular instance of \textsc{Exact Cover} is a family of \(m\) sets \(F_{n,d,k}=\{S_j\subseteq\{1,\ldots,n\}\}\), where each subset has size \(k\) and each \(1\leq i\leq n\) is contained in \(d\) of the \(S_j\). It is satisfiable if there is a subset \(T\subseteq\{1,\ldots,n\}\) such that \(|T\cap S_j|=1\) for all \(j\). Alternately, we can consider it a \(d\)-regular instance of \textsc{Positive} 1-\textsc{in}-\(k\) SAT, i.e., a Boolean formula with \(m\) clauses and \(n\) variables where each clause contains \(k\) variables and demands that exactly one of them is true. We determine the satisfiability threshold for random instances of this type with \(k>2\). Letting \[ d^\star=\frac{\ln k}{(k-1)(-\ln(1-1/k))}+1 \] we show that \(F_{n,d,k}\) is satisfiable with high probability if \(d<d^\star\) and unsatisfiable with high probability if \(d>d^\star\). We do this with a simple application of the first and second moment methods, boosting the probability of satisfiability below \(d^\star\) to \(1-o(1)\) using the small subgraph conditioning method.
0 references
random structures
0 references
phase transitions
0 references
Boolean formulas
0 references
satisfiability
0 references
NP-complete problems
0 references
second moment method
0 references
small subgraph conditioning
0 references