Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.15940 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909619530498048 |
|---|---|
| author | Basse-O'Connor, Andreas Skjøtt, Mette |
| author_facet | Basse-O'Connor, Andreas Skjøtt, Mette |
| contents | The random $k$-SAT problem serves as a model that represents the 'typical' $k$-SAT instances. This model is thought to undergo a phase transition as the clause density changes, and it is believed that the random $k$-SAT problem is primarily difficult to solve near this critical phase. In this paper, we introduce a weak formulation of degrees of freedom for random $k$-SAT problems and demonstrate that the critical random $2$-SAT problem has $\sqrt[3]{n}$ degrees of freedom. This quantity represents the maximum number of variables that can be assigned truth values without affecting the formula's satisfiability. Notably, the value of $\sqrt[3]{n}$ differs significantly from the degrees of freedom in random $2$-SAT problems sampled below the satisfiability threshold, where the corresponding value equals $\sqrt{n}$. Thus, our result underscores the significant shift in structural properties and variable dependency as satisfiability problems approach criticality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_15940 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Degrees of Freedom for Critical Random 2-SAT Basse-O'Connor, Andreas Skjøtt, Mette Probability The random $k$-SAT problem serves as a model that represents the 'typical' $k$-SAT instances. This model is thought to undergo a phase transition as the clause density changes, and it is believed that the random $k$-SAT problem is primarily difficult to solve near this critical phase. In this paper, we introduce a weak formulation of degrees of freedom for random $k$-SAT problems and demonstrate that the critical random $2$-SAT problem has $\sqrt[3]{n}$ degrees of freedom. This quantity represents the maximum number of variables that can be assigned truth values without affecting the formula's satisfiability. Notably, the value of $\sqrt[3]{n}$ differs significantly from the degrees of freedom in random $2$-SAT problems sampled below the satisfiability threshold, where the corresponding value equals $\sqrt{n}$. Thus, our result underscores the significant shift in structural properties and variable dependency as satisfiability problems approach criticality. |
| title | Degrees of Freedom for Critical Random 2-SAT |
| topic | Probability |
| url | https://arxiv.org/abs/2505.15940 |