Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-068 | 4th May 2026 21:22

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time

RSS-Feed




TR26-068
Authors: John Hitchcock
Publication: 4th May 2026 21:51
Downloads: 48
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint