Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
John M. Hitchcock · 2026
Read Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time by John M. Hitchcock (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03306.txt.
Introduction
John M. Hitchcock shows that languages needing exponential-size circuits are typical inside symmetric exponential time, in the resource-bounded category sense. Category here measures largeness through a game, extending classic results that placed the same circuit class as small inside a larger space class.
Hitchcock defines smallness against single-valued strategies for the symmetric class and turns a known range avoidance algorithm into a winning game strategy. That makes the exponential circuit class meager there, so its complement, languages that truly need huge circuits, is comeager and thus typical. The note ties circuit lower bounds to descriptive largeness.
Catalog record
| CREATOR | John M. Hitchcock |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 15 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.03306
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time John M. Hitchcock Abstract Lutz (1987) introduced resource-bounded category and showed the circuit size class 𝖲𝖨𝖹𝖤 ( 2 n n ) \mathsf{SIZE}(\frac{2^{n}}{n}) is meager within 𝖤𝖲𝖯𝖠𝖢𝖤 \mathsf{ESPACE} . Li (2024) established that the symmetric alternation class 𝖲 2 𝖤 \mathsf{S}^{\mathsf{E}}_{2} contains problems requiring circuits of size 2 n n \frac{2^{n}}{n} . In this note, we extend resource-bounded category to 𝖲 2 𝖤 \mathsf{S}^{\mathsf{E}}_{2} by defining meagerness relative to single-valued 𝖥𝖲 2 𝖯 \mathsf{FS}^{\mathsf{P}}_{2} strategies in the Banach-Mazur game. We show that Li’s 𝖥𝖲 2 𝖯 \mathsf{FS}^{\mathsf{P}}_{2} algorithm for the Range Avoidance problem yields a winning strategy, proving that 𝖲𝖨𝖹𝖤 ( 2 n n ) \mathsf{SIZE}(\frac{2^{n}}{n}) is meager in 𝖲 2 𝖤 \mathsf{S}^{\mathsf{E}}_{2} . Consequently, languages requiring exponential-size circuits are comeager in 𝖲 2 𝖤 \mathsf{S}^{\mathsf{E}}_{2} : they are typical with respect to resource-bounded category. 1 Introduction Resource-bounded category, introduced by Lutz [ 14 , 15 , 16 ] , provides a way to analyze the typical properties of complexity classes using topological notions of size. Lutz showed that the class \mathsf{SIZE}(\frac{2^{n}}{n}) of languages decidable by circuits of size \frac{2^{n}}{n} is meager within the exponential-space class \mathsf{ESPACE} . Theorem 1.1 . (Lutz [ 14 , 15 , 16 ] ) \mathsf{SIZE}(\frac{2^{n}}{n}) is meager in \mathsf{ESPACE} . The symmetric exponential-time class \mathsf{S}^{\mathsf{E}}_{2} is an exponential version of the class \mathsf{S}^{\mathsf{P}}_{2} [ 5 , 21 ] and it lies between \mathsf{E} and \mathsf{ESPACE} . Building on work by Korten [ 12 ] and Chen, Hirahara, and Ren [ 6 ] , Li [ 13 ] recently proved that \mathsf{S}^{\mathsf{E}}_{2} contains languages that require near-maximum circuit size. Theorem 1.2 . (Li [ 13 ] ) \mathsf{S}^{\mathsf{E}}_{2}\not\subseteq\mathsf{SIZE}(\frac{2^{n}}{n}) . This solved a longstanding open problem to show the second level of the exponential-time hierarchy requires exponential-size circuits [ 10 , 3 , 19 , 20 , 9 , 1 , 2 ] . Li’s proof technique involves constructing a hard language using a single-valued \mathsf{FS}^{\mathsf{P}}_{2} algorithm (a function problem analogue of \mathsf{S}^{\mathsf{P}}_{2} ). Given these developments, a natural question is whether the category framework can be refined to operate within \mathsf{S}^{\mathsf{E}}_{2} . Can we show that languages requiring large circuits are not just present, but are in fact typical within \mathsf{S}^{\mathsf{E}}_{2} ? In this note, we answer this question affirmatively. We adapt the resource-bounded category machinery to the class \mathsf{S}^{\mathsf{E}}_{2} by defining meagerness relative to single-valued \mathsf{FS}^{\mathsf{P}}_{2} -computable constructors in the Banach-Mazur game. Our main result shows that, analogous to Lutz’s result for \mathsf{ESPACE} , small circuits are atypical within \mathsf{S}^{\mathsf{E}}_{2} . Theorem 1.3 . \mathsf{SIZE}(\frac{2^{n}}{n}) is meager in \mathsf{S}^{\mathsf{E}}_{2} . We prove this by demonstrating that Li’s single-valued \mathsf{FS}^{\mathsf{P}}_{2} algorithm for the range avoidance problem [ 12 , 6 ] provides a winning strategy against \mathsf{SIZE}(\frac{2^{n}}{n}) in the appropriate Banach-Mazur game. Thus, languages requiring exponential-size circuits are not just present in \mathsf{S}^{\mathsf{E}}_{2} —they are typical in the sense of resource-bounded category: the class of such languages is comeager in \mathsf{S}^{\mathsf{E}}_{2} . This paper is organized as follows. We present preliminaries on resource-bounded category and symmetric alternation in Section 2 . Our results are in Section 3 . We conclude in Section 4 with an open question about extending our results to resource-bounded measure. 2 Preliminaries 2.1 Resource-Bounded Category Resource-bounded category was introduced by Lutz [ 14 , 15 , 16 ] . The Cantor space \mathsf{C} is the set of all infinite binary sequences. A language (or decision problem ) is a subset of \{0,1\}^{*} . We identify each language with the element of Cantor space that is its characteristic sequence according to the standard enumeration s_{0}=\lambda,s_{1}=0,s_{2}=1,s_{3}=00,\ldots of \{0,1\}^{*} . In this way, complexity classes (sets of languages) are viewed as subsets of Cantor space. Baire category classifies sets into two types: first category and second category . First category sets are also commonly called meager . A set is meager if it is a countable union of nowhere dense sets. An equivalent definition comes from Banach-Mazur games using functions called constructors. Definition 2.1 . A constructor is a total, single-valued function \delta:\{0,1\}^{*}\to\{0,1\}^{*} which satisfies x\underset{\neq}{\sqsubset}\delta(x) for all x\in\{0,1\}^{*} . The result of a constructor is the unique sequence R(\delta)\in\mathsf{C} that extends \delta^{(n)}(\lambda) for all n . Let X\subseteq\mathsf{C} and let \Gamma_{\rm I} and \Gamma_{\rm II} be two classes of functions. In the Banach-Mazur game G[X;\Gamma_{\rm I},\Gamma_{\rm II}] there are two players I and II. A strategy in the game is a constructor. In a play of the game, player I chooses a strategy \gamma\in\Gamma_{\rm I} and player II chooses a strategy \delta\in\Gamma_{\rm II} . The result of this play is the sequence R(\gamma,\delta)=R(\delta\circ\gamma) . Intuitively, the result is the sequence obtained when the two players start with the empty string and take turns extending it with their strategies. A winning strategy for player II is a strategy \delta\in\Gamma_{\rm II} such that for every \gamma\in\Gamma_{\rm I} , R(\gamma,\delta)\not\in X . Theorem 2.2 . (Banach and Mazur) A class X\subseteq\mathsf{C} is meager if and only if player II has a winning strategy in the game G[X;{\mathsf{all}},{\mathsf{all}}] . In resource-bounded category, \Delta denotes a resource bound [ 17 , 16 ] . Examples of \Delta include: \displaystyle{\mathsf{all}} \displaystyle= \displaystyle\{f\mid f:\{0,1\}^{*}\to\{0,1\}^{*}\} \displaystyle{\mathsf{p}} \displaystyle= \displaystyle\{f\mid f\textrm{ is polynomial-time computable}\} \displaystyle{\mathsf{pspace}} \displaystyle= \displaystyle\{f\mid f\textrm{ is polynomial-space computable}\} For a resource bound \Delta , we define the result class R(\Delta)=\{R(\delta)\mid\delta\in\Delta\textrm{ is a constructor}\}. Then R({\mathsf{all}})=\mathsf{C} , R({\mathsf{p}})=\mathsf{E} , and R({\mathsf{pspace}})=\mathsf{ESPACE} [ 16 ] . Resource-bounded category [ 16 ] is defined by requiring player II’s winning strategy to be computable within a resource bound \Delta . Definition 2.3 . Let X\subseteq\mathsf{C} and let \Delta be a resource bound. 1. X is \Delta -meager if player II has a winning strategy in the game G[X;{\mathsf{all}},\Delta] . 2. X is \Delta -comeager if X^{c} is \Delta -meager. 3. X is meager in R(\Delta) if X\cap R(\Delta) is \Delta -meager. 4. X is comeager in R(\Delta) if X^{c} is meager in R(\Delta) . The resource-bounded Baire category theorem [ 16 ] tells us that R(\Delta) is not \Delta -meager. 2.2 Symmetric Alternation Symmetric alternation is a concept in computational complexity theory introduced independently by Canetti [ 5 ] and Russell and Sundaram [ 21 ] with different, but equivalent definitions [ 4 ] . We follow the definition due to Canetti. Definition 2.4 . Let T\colon\mathbb{N}\to\mathbb{N} . We say that a language L\in\mathsf{S}_{2}\mathsf{TIME}[T(n)] if there exists an O(T(n)) -time verifier V(x,\pi_{1},\pi_{2}) that takes x\in\{0,1\}^{n} and \pi_{1},\pi_{2}\in\{0,1\}^{T(n)} as input, satisfying (\exists\pi_{1})(\forall\pi_{2})V(x,\pi_{1},\pi_{2})=\chi_{L}(x) and (\exists\pi_{2})(\forall\pi_{1})V(x,\pi_{1},\pi_{2})=\chi_{L}(x). Definition 2.5 . We define the symmetric alternation complexity classes \mathsf{S}^{\mathsf{P}}_{2}=\bigcup_{c=1}^{\infty}\mathsf{S}_{2}\mathsf{TIME}[n^{c}]. and \mathsf{S}^{\mathsf{E}}_{2}=\bigcup_{c=1}^{\infty}\mathsf{S}_{2}\mathsf{TIME}[2^{cn}]. Symmetric alternation is used to compute single-valued functions as follows [ 13 ] . Definition 2.6 . A single‐valued \mathsf{FS}^{\mathsf{P}}_{2} algorithm A is specified by a polynomial \ell(\cdot) together with a polynomial‐time verifier V_{A}(x,\pi_{1},\pi_{2}). On input x\in\{0,1\}^{*} , we say that A outputs a string y_{x}\in\{0,1\}^{*} if the following two conditions hold: 1. There exists \pi_{1}\in\{0,1\}^{\ell(|x|)} such that for every \pi_{2}\in\{0,1\}^{\ell(|x|)} , V_{A}(x,\pi_{1},\pi_{2})\;\allowbreak=\;y_{x}. 2. There exists \pi_{2}\in\{0,1\}^{\ell(|x|)} such that for every \pi_{1}\in\{0,1\}^{\ell(|x|)} , V_{A}(x,\pi_{1},\pi_{2})\;=\;y_{x}. Note that Section 2.2 prescribes a single-valued \mathsf{FS}^{\mathsf{P}}_{2} algorithm for \chi_{L} . Li [ 13 ] used a single-valued \mathsf{FS}^{\mathsf{P}}_{2} algorithm for the range avoidance problem [ 12 , 6 ] to prove Theorem