Saved in:
| Main Author: | |
|---|---|
| Format: | Recurso digital |
| Language: | English |
| Published: |
Zenodo
2025
|
| Online Access: | https://doi.org/10.5281/zenodo.17200765 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |