| _version_ | 1866902217053700096 |
|---|---|
| author | Fernandes, Ricardo Miguel Machado |
| author_facet | Fernandes, Ricardo Miguel Machado |
| contents | <p>This work presents a physics-informed perspective on the <span><span>PP</span><span><span><span>P</span></span></span></span> vs.\ <span><span>NPNP</span><span><span><span>NP</span></span></span></span> problem.<br>It introduces the <em>Medium-Access Machine (MAM)</em> model, based on unitarity (information conservation) and locality (bounded access), and shows its equivalence to two-sided polynomial indexability.<br>The framework highlights computation as an <em>observer-limited process</em>: while the universe may in principle contain the full truth of satisfiability, observers constrained by physical law cannot access enough of it in polynomial time.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_17088727 |
| institution | Zenodo |
| language | |
| publishDate | 2025 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | NP vs. coNP as an Observer Constraint: A Physics-Informed Framework Fernandes, Ricardo Miguel Machado P vs NP NP vs coNP computational complexity physics of computation <p>This work presents a physics-informed perspective on the <span><span>PP</span><span><span><span>P</span></span></span></span> vs.\ <span><span>NPNP</span><span><span><span>NP</span></span></span></span> problem.<br>It introduces the <em>Medium-Access Machine (MAM)</em> model, based on unitarity (information conservation) and locality (bounded access), and shows its equivalence to two-sided polynomial indexability.<br>The framework highlights computation as an <em>observer-limited process</em>: while the universe may in principle contain the full truth of satisfiability, observers constrained by physical law cannot access enough of it in polynomial time.</p> |
| title | NP vs. coNP as an Observer Constraint: A Physics-Informed Framework |
| topic | P vs NP NP vs coNP computational complexity physics of computation |
| url | https://doi.org/10.5281/zenodo.17088727 |