Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2504.11979 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915246035173376 |
|---|---|
| author | Basse-O'Connor, Andreas Overgaard, Tobias Lindhardt Skjøtt, Mette |
| author_facet | Basse-O'Connor, Andreas Overgaard, Tobias Lindhardt Skjøtt, Mette |
| contents | We consider the random $k$-SAT problem with $n$ variables, $m=m(n)$ clauses, and clause density $α=\lim_{n\to\infty}m/n$ for $k=2,3$. It is known that if $α$ is small enough, then the random $k$-SAT problem admits a solution with high probability, which we interpret as the problem being under-constrained. In this paper, we quantify exactly how under-constrained the random $k$-SAT problems are by determining their degrees of freedom, which we define as the threshold for the number of variables we can fix to an arbitrary value before the problem no longer is solvable with high probability. We show that the random $2$-SAT and $3$-SAT problems have $n/m^{1/2}$ and $n/m^{1/3}$ degrees of freedom, respectively. Our main result is an explicit computation of the corresponding threshold functions. Our result shows that the threshold function for the random $2$-SAT problem is regular, while it is non-regular for the random $3$-SAT problem. By regular, we mean continuous and analytic on the interior of its support. This result shows that the random $3$-SAT problem is more sensitive to small changes in the clause density $α$ than the random $2$-SAT problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_11979 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Regularity of Random 2-SAT and 3-SAT Basse-O'Connor, Andreas Overgaard, Tobias Lindhardt Skjøtt, Mette Probability Discrete Mathematics 60K35 (Primary) 82B26, 68R07 (Secondary) We consider the random $k$-SAT problem with $n$ variables, $m=m(n)$ clauses, and clause density $α=\lim_{n\to\infty}m/n$ for $k=2,3$. It is known that if $α$ is small enough, then the random $k$-SAT problem admits a solution with high probability, which we interpret as the problem being under-constrained. In this paper, we quantify exactly how under-constrained the random $k$-SAT problems are by determining their degrees of freedom, which we define as the threshold for the number of variables we can fix to an arbitrary value before the problem no longer is solvable with high probability. We show that the random $2$-SAT and $3$-SAT problems have $n/m^{1/2}$ and $n/m^{1/3}$ degrees of freedom, respectively. Our main result is an explicit computation of the corresponding threshold functions. Our result shows that the threshold function for the random $2$-SAT problem is regular, while it is non-regular for the random $3$-SAT problem. By regular, we mean continuous and analytic on the interior of its support. This result shows that the random $3$-SAT problem is more sensitive to small changes in the clause density $α$ than the random $2$-SAT problem. |
| title | On the Regularity of Random 2-SAT and 3-SAT |
| topic | Probability Discrete Mathematics 60K35 (Primary) 82B26, 68R07 (Secondary) |
| url | https://arxiv.org/abs/2504.11979 |