2024/01/22 by Jun Le Goh, Goh, Jun Le, Arno Pauly +3
Computer Science · Engineering · Mathematics · #03D30 03D78 06A75 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Rings, Modules, and Algebras #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2401.11807
openalex publication_date 2024/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We explore the Weihrauch degree of the problems ``find a bad sequence in a non-well quasi order'' (BS) and ``find a descending sequence in an ill-founded linear order'' (DS). We prove that DS is strictly Weihrauch reducible to BS, correcting our mistaken claim in [arXiv:2010.03840]. This is done by separating their respective first-order parts. On the other hand, we show that BS and DS have the same finitary and deterministic parts, confirming that BS and DS have very similar uniform computational strength. We prove that König's lemma KL and the problem wList2ℕ,≤ω of enumerating a given non-empty countable closed subset of 2ℕ are not Weihrauch reducible to DS or BS, resolving two main open questions raised in [arXiv:2010.03840]. We also answer the question, raised in [arXiv:1804.10968], on the existence of a ``parallel quotient'' operator, and study the behavior of BS and DS under the quotient with some known problems.