Complexity of deep computations via topology of function spaces

Read full text
Authors: Eduardo Duéñez, José Iovino, Tonatiuh Matos-Wiederhold, Luciano Salvetti, Franklin D. Tall
Cited by: 0

Abstract

We use topological methods to study complexity of deep computations and limit computations. We use topology of function spaces, specifically, the classification Rosenthal compacta, to identify new complexity classes. We use the language of model theory, specifically, the concept of \emph{independence} from Shelah's classification theory, to translate between topology and computation. We use the theory of Rosenthal compacta to characterize approximablility of deep computations, both deterministically and probabilistically.

Fields of Study & Subjects

Computability Logic AI Algorithms Advanced Topology and Set Theory Topological and Geometric Data Analysis

Publication details

Journal / source
arXiv (Cornell University)
Publication date
2 January 2026
Document type
Preprint