Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2505.15940 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- 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.