Structural Non-Compressibility of Search/From Exposure Time to Rejection Coordinates
Fuente:
Zenodo
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Recurso digital |
| Publicado: |
Zenodo
2026
|
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866901725637509120 |
|---|---|
| author | KEI, SIRAISHI |
| author_facet | KEI, SIRAISHI |
| contents | <p><strong>Description</strong></p> <p>This repository contains the first public release (v1.0) of a research manuscript addressing a structural aspect of the P vs NP problem: the inherent non-compressibility of search.</p> <p>Rather than claiming an immediate separation result, the manuscript presents a complete and inspectable proof route identifying <strong>structural limits that prevent parallel compression of search beyond linear bounds under polynomial-time reductions</strong>. The core contribution is a <em>No-Mass-Determination theorem</em>, which establishes that any deterministic protocol with bounded communication can certify only a limited number of candidate eliminations per transcript.</p> <p>The approach is based on the following components:</p> <ul> <li> <p>candidate-specific rejection coordinates,</p> </li> <li> <p>a self-contained monochromatic rectangle bound for the inner product function,</p> </li> <li> <p>a weak and unconditional structural condition (t-wise regularity) imposed solely on the rejection set.</p> </li> </ul> <p>Notably, the commonly assumed block-independence condition is entirely removed. The remaining regularity requirement is realized without cryptographic assumptions, via polynomial evaluation over finite fields. All assumptions are explicitly stated and minimized, and the sole technical focal point is fully formalized through an exact counting argument.</p> <p>This version is released to enable open verification and scrutiny by the theoretical computer science community. Subsequent versions may refine exposition or address feedback, while preserving the core results.</p> <p>The present framework was originally motivated by concrete instantiations, such as layered CNF families, which serve as minimal structured examples illustrating exploration persistence. However, the results presented here are formulated at an abstract level and do not rely on any specific problem class.</p> <p><strong>Keywords</strong>: P vs NP, search complexity, communication complexity, lower bounds, succinct computation</p> <p> </p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_18203617 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | Structural Non-Compressibility of Search/From Exposure Time to Rejection Coordinates KEI, SIRAISHI <p><strong>Description</strong></p> <p>This repository contains the first public release (v1.0) of a research manuscript addressing a structural aspect of the P vs NP problem: the inherent non-compressibility of search.</p> <p>Rather than claiming an immediate separation result, the manuscript presents a complete and inspectable proof route identifying <strong>structural limits that prevent parallel compression of search beyond linear bounds under polynomial-time reductions</strong>. The core contribution is a <em>No-Mass-Determination theorem</em>, which establishes that any deterministic protocol with bounded communication can certify only a limited number of candidate eliminations per transcript.</p> <p>The approach is based on the following components:</p> <ul> <li> <p>candidate-specific rejection coordinates,</p> </li> <li> <p>a self-contained monochromatic rectangle bound for the inner product function,</p> </li> <li> <p>a weak and unconditional structural condition (t-wise regularity) imposed solely on the rejection set.</p> </li> </ul> <p>Notably, the commonly assumed block-independence condition is entirely removed. The remaining regularity requirement is realized without cryptographic assumptions, via polynomial evaluation over finite fields. All assumptions are explicitly stated and minimized, and the sole technical focal point is fully formalized through an exact counting argument.</p> <p>This version is released to enable open verification and scrutiny by the theoretical computer science community. Subsequent versions may refine exposition or address feedback, while preserving the core results.</p> <p>The present framework was originally motivated by concrete instantiations, such as layered CNF families, which serve as minimal structured examples illustrating exploration persistence. However, the results presented here are formulated at an abstract level and do not rely on any specific problem class.</p> <p><strong>Keywords</strong>: P vs NP, search complexity, communication complexity, lower bounds, succinct computation</p> <p> </p> |
| title | Structural Non-Compressibility of Search/From Exposure Time to Rejection Coordinates |
| url | https://doi.org/10.5281/zenodo.18203617 |