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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references