On the complexity of Medvedev reducibility
Abstract
The Medvedev lattice is a tool used to classify the complexity of effective closed sets. In this article, we are interested in the complexity of using this tool. In particular, we study the complexity of deciding whether two effective closed sets have the same degree, when one is fixed and the other is given as input. This problem is naturally~Σ03, and among other results, we show that for all degrees except the maximal one, the problem reaches its maximal complexity. It turns out that the argument is not uniform and depends on the self-similarity of the fixed degree, a notion that we introduce in this article. The complexity of having maximal degree is particularly difficult to establish, but we obtain a lower bound that almost matches the upper bound. We also show that deciding whether an effective closed set has a degree incomparable with a fixed degree d is Π03-complete whenever 0s <s d <s 1s.
Related
- Medvedev degrees of SFTs on cocompact Fuchsian groups
- Medvedev logic is undecidable
- Medvedev Logic is Not Decidable. It is π01 -complete. Who Would Have Guessed?
- Reducibility of linear representations, free ideals, and Kippenhahn's conjecture
- Reducibility and Diagonal Equality Strata for Finite Jacobi Pencils
BibTeX
@misc{pallen2026complexity,
title = {{On the complexity of Medvedev reducibility}},
author = {Remi Pallen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32522},
eprint = {2610.32522},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32522},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the complexity of Medvedev reducibility
AU - Remi Pallen
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32522
UR - https://arxiv.org/abs/2610.32522
AB - The Medvedev lattice is a tool used to classify the complexity of effective closed sets. In this article, we are interested in the complexity of using this tool. In particular, we study the complexity of deciding whether two effective closed sets have the same degree, when one is fixed and the other is given as input. This problem is naturally~Σ^0_3, and among other results, we show that for all degrees except the maximal one, the problem reaches its maximal complexity. It turns out that the argument is not uniform and depends on the self-similarity of the fixed degree, a notion that we introduce in this article. The complexity of having maximal degree is particularly difficult to establish, but we obtain a lower bound that almost matches the upper bound. We also show that deciding whether an effective closed set has a degree incomparable with a fixed degree d is Π^0_3-complete whenever 0_s <_s d <_s 1_s.
ER -