2016/10/05 by Achilles A. Beros, Beros, Achilles A., Konstantinos A. Beros +1 · 1 citation
Computer Science · Mathematics · #03D30 #03D80 #Coding theory and cryptography #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #math.LO #msc:03D30 #msc:03D80 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1610.01650
13 pages
arxiv created 2016/10/05 · openalex publication_date 2016/10/05 · arxiv updated 2016/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We examine sets of codes such that certain properties are invariant under the choice of oracle from a range of possible oracles and establish a connection between such codes and Medvedev reductions. In examing the complexity of such sets of universal codes, we prove completeness results at various levels of the arithmetic hierarchy as well as two general theorems for obtaining Π11-completeness for sets of universal codes. Among other corollaries, we show that the set of codes for Medvedev reductions of bi-immune sets to DNC functions is Π11-complete.