Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Recurso digital |
| Lingua: | inglese |
| Pubblicazione: |
Zenodo
2025
|
| Accesso online: | https://doi.org/10.5281/zenodo.17200765 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866902159510994944 |
|---|---|
| author | Dmitry, Khanukov |
| author_facet | Dmitry, Khanukov |
| contents | <p>This is a working preprint of "Proving P ≠ NP via the Family Collision-Entropy Lemma."<br>We present a novel combinatorial argument showing that any family of Boolean functions with sufficiently low collision entropy can be covered by subexponentially many monochromatic rectangles, and use this to resolve the final barrier in separating P from NP. All core lemmas (Entropy-Drop, Sunflower, Core Agreement) have been fully formalized in Lean 4, and the repository includes complete proof scripts and auxiliary definitions. Future versions will finalize the formal proof of the MCSP lower bound and remove all remaining admitted steps.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_17200765 |
| institution | Zenodo |
| language | eng |
| publishDate | 2025 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | Outline of a Proof that P <> NP via the Family Collision-Entropy Dmitry, Khanukov <p>This is a working preprint of "Proving P ≠ NP via the Family Collision-Entropy Lemma."<br>We present a novel combinatorial argument showing that any family of Boolean functions with sufficiently low collision entropy can be covered by subexponentially many monochromatic rectangles, and use this to resolve the final barrier in separating P from NP. All core lemmas (Entropy-Drop, Sunflower, Core Agreement) have been fully formalized in Lean 4, and the repository includes complete proof scripts and auxiliary definitions. Future versions will finalize the formal proof of the MCSP lower bound and remove all remaining admitted steps.</p> |
| title | Outline of a Proof that P <> NP via the Family Collision-Entropy |
| url | https://doi.org/10.5281/zenodo.17200765 |