Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
For complexity theorists, it establishes that exponential circuit complexity is the norm within S^E_2, extending known meager results from ESPACE.
The paper extends resource-bounded category to the complexity class S^E_2 and proves that languages requiring exponential-size circuits are comeager (typical) in S^E_2, building on Li's algorithm for the Range Avoidance problem.
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.