Complexity of deep computations via topology of function spaces

Eduardo Dueñez, José Iovino, Tonatiuh Matos-Wiederhold, Luciano Salvetti, Franklin D. Tall

arXivarxiv/2601.00528Jan 2, 2026math.LOscore 0

We use topological methods to study complexity of deep computations and limit computations. We use topology of function spaces, specifically, the classification of 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.

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2601.00528
curl -X POST /api/v1/records/arxiv/2601.00528/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.00528/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'