Abstract:
Lutz (1987) introduced resource-bounded category and showed the circuit size class \( \mathsf{SIZE}(2^n / n) \) is meager within \( \mathsf{ESPACE} \). Li (2024) established that the symmetric alternation class \( \mathsf{S}^{\mathsf{E}}_2 \) contains problems requiring circuits of size \( 2^n / n \).
In this note, we extend resource-bounded category to \( \mathsf{S}^{\mathsf{E}}_2 \) by defining meagerness relative to single-valued \( \mathsf{FS}^{\mathsf{P}}_2 \) strategies in the Banach–Mazur game. We show that Li’s \( \mathsf{FS}^{\mathsf{P}}_2 \) algorithm for the Range Avoidance problem yields a winning strategy, proving that \( \mathsf{SIZE}(2^n / n) \) is meager in \( \mathsf{S}^{\mathsf{E}}_2 \).
Consequently, languages requiring exponential-size circuits are comeager in \( \mathsf{S}^{\mathsf{E}}_2 \): they are typical with respect to resource-bounded category.