2024/07/04 by Arno Pauly, Pauly, Arno · 1 citation
Computer Science · Mathematics · #03D30 #05C55 #Algebraic Geometry and Number Theory #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2407.03722
openalex publication_date 2024/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the complexity of the computational task ``Given a colouring c : ℚ → k, find a monochromatic S ⊆ ℚ such that (S,<) ≅ (ℚ,<)''. The framework is Weihrauch reducibility. Our results answer some open questions recently raised by Gill, and by Dzhafarov, Solomon and Valenti.