The Satisfiability Threshold fork-XORSAT
| Autor: | Boris Pittel, Gregory B. Sorkin |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Statistics and Probability
Hypergraph Phase transition Applied Mathematics Probability (math.PR) 010102 general mathematics 0102 computer and information sciences 01 natural sciences Satisfiability Theoretical Computer Science Combinatorics Computational Theory and Mathematics Random systems Computer Science::Discrete Mathematics 010201 computation theory & mathematics FOS: Mathematics Mathematics - Combinatorics QA Mathematics Combinatorics (math.CO) 0101 mathematics Mathematics - Probability Variable (mathematics) Mathematics |
| Zdroj: | Combinatorics, Probability and Computing. 25:236-268 |
| ISSN: | 1469-2163 0963-5483 |
| DOI: | 10.1017/s0963548315000097 |
| Popis: | We consider "unconstrained" random $k$-XORSAT, which is a uniformly random system of $m$ linear non-homogeneous equations in $\mathbb{F}_2$ over $n$ variables, each equation containing $k \geq 3$ variables, and also consider a "constrained" model where every variable appears in at least two equations. Dubois and Mandler proved that $m/n=1$ is a sharp threshold for satisfiability of constrained 3-XORSAT, and analyzed the 2-core of a random 3-uniform hypergraph to extend this result to find the threshold for unconstrained 3-XORSAT. We show that $m/n=1$ remains a sharp threshold for satisfiability of constrained $k$-XORSAT for every $k\ge 3$, and we use standard results on the 2-core of a random $k$-uniform hypergraph to extend this result to find the threshold for unconstrained $k$-XORSAT. For constrained $k$-XORSAT we narrow the phase transition window, showing that $m-n \to -\infty$ implies almost-sure satisfiability, while $m-n \to +\infty$ implies almost-sure unsatisfiability. Comment: Version 2 adds sharper phase transition result, new citation in literature survey, and improvements in presentation; removes Appendix treating k=3 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|