Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Recurso digital |
| Langue: | anglais |
| Publié: |
Zenodo
2025
|
| Accès en ligne: | https://doi.org/10.5281/zenodo.17200765 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
Table des matières:
- <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>