The number of random 2-SAT solutions is asymptotically log-normal
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913508952637440 |
|---|---|
| author | Chatterjee, Arnab Coja-Oghlan, Amin Müller, Noela Riddlesden, Connor Rolvien, Maurice Zakharov, Pavel Zhu, Haodong |
| author_facet | Chatterjee, Arnab Coja-Oghlan, Amin Müller, Noela Riddlesden, Connor Rolvien, Maurice Zakharov, Pavel Zhu, Haodong |
| contents | We prove that throughout the satisfiable phase, the logarithm of the number of satisfying assignments of a random 2-SAT formula satisfies a central limit theorem. This implies that the log of the number of satisfying assignments exhibits fluctuations of order $\sqrt n$, with $n$ the number of variables. The formula for the variance can be evaluated effectively. By contrast, for numerous other random constraint satisfaction problems the typical fluctuations of the logarithm of the number of solutions are {\em bounded} throughout all or most of the satisfiable regime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_03302 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The number of random 2-SAT solutions is asymptotically log-normal Chatterjee, Arnab Coja-Oghlan, Amin Müller, Noela Riddlesden, Connor Rolvien, Maurice Zakharov, Pavel Zhu, Haodong Discrete Mathematics Combinatorics Probability 05C80 We prove that throughout the satisfiable phase, the logarithm of the number of satisfying assignments of a random 2-SAT formula satisfies a central limit theorem. This implies that the log of the number of satisfying assignments exhibits fluctuations of order $\sqrt n$, with $n$ the number of variables. The formula for the variance can be evaluated effectively. By contrast, for numerous other random constraint satisfaction problems the typical fluctuations of the logarithm of the number of solutions are {\em bounded} throughout all or most of the satisfiable regime. |
| title | The number of random 2-SAT solutions is asymptotically log-normal |
| topic | Discrete Mathematics Combinatorics Probability 05C80 |
| url | https://arxiv.org/abs/2405.03302 |