On the Incompressibility of Truth With Application to Circuit Complexity
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918264339169280 |
|---|---|
| author | Tonon, Luke |
| author_facet | Tonon, Luke |
| contents | We revisit the fundamentals of Circuit Complexity and the nature of efficient computation from a fresh perspective. We present a framework for understanding Circuit Complexity through the lens of Information Theory with analogies to results in Kolmogorov Complexity, viewing circuits as descriptions of truth tables, encoded in logical gates and wires, rather than purely computational devices. From this framework, we re-prove some existing Circuit Complexity bounds, explain what the optimal circuits for most boolean functions look like structurally, give an explicit boolean function family that requires exponential circuits, and explain the aforementioned results in a unifying intuition that re-frames time entirely. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21738 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Incompressibility of Truth With Application to Circuit Complexity Tonon, Luke Computational Complexity Discrete Mathematics We revisit the fundamentals of Circuit Complexity and the nature of efficient computation from a fresh perspective. We present a framework for understanding Circuit Complexity through the lens of Information Theory with analogies to results in Kolmogorov Complexity, viewing circuits as descriptions of truth tables, encoded in logical gates and wires, rather than purely computational devices. From this framework, we re-prove some existing Circuit Complexity bounds, explain what the optimal circuits for most boolean functions look like structurally, give an explicit boolean function family that requires exponential circuits, and explain the aforementioned results in a unifying intuition that re-frames time entirely. |
| title | On the Incompressibility of Truth With Application to Circuit Complexity |
| topic | Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2511.21738 |