Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.03306 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911646790713344 |
|---|---|
| author | Hitchcock, John M. |
| author_facet | Hitchcock, John M. |
| contents | Lutz (1987) introduced resource-bounded category and showed the circuit size class SIZE($\frac{2^n}{n}$) is meager within ESPACE. Li (2024) established that the symmetric alternation class $S^E_2$ contains problems requiring circuits of size $\frac{2^n}{n}$.
In this note, we extend resource-bounded category to $S^E_2$ by defining meagerness relative to single-valued $FS^P_2$ strategies in the Banach-Mazur game. We show that Li's $FS^P_2$ algorithm for the Range Avoidance problem yields a winning strategy, proving that SIZE($\frac{2^n}{n}$) is meager in $S^E_2$.
Consequently, languages requiring exponential-size circuits are comeager in $S^E_2$: they are typical with respect to resource-bounded category. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_03306 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time Hitchcock, John M. Computational Complexity Lutz (1987) introduced resource-bounded category and showed the circuit size class SIZE($\frac{2^n}{n}$) is meager within ESPACE. Li (2024) established that the symmetric alternation class $S^E_2$ contains problems requiring circuits of size $\frac{2^n}{n}$. In this note, we extend resource-bounded category to $S^E_2$ by defining meagerness relative to single-valued $FS^P_2$ strategies in the Banach-Mazur game. We show that Li's $FS^P_2$ algorithm for the Range Avoidance problem yields a winning strategy, proving that SIZE($\frac{2^n}{n}$) is meager in $S^E_2$. Consequently, languages requiring exponential-size circuits are comeager in $S^E_2$: they are typical with respect to resource-bounded category. |
| title | Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2605.03306 |