← Back to arXiv
arXivLogicarXiv:2609.00419

Every Nonrecursive Many-One Degree Contains Either One or Infinitely Many Finite-One Degrees

Computability theory studies which mathematical problems can be solved by algorithms and how different unsolvable problems relate to one another in terms of difficulty. One way to compare the difficulty of problems is through "reductions," where you show that solving one problem would let you solve another. A "many-one reduction" from problem A to problem B means there is a computable function that converts any question about A into a question about B. Problems that are equally difficult under this notion are grouped into "many-one degrees." A stricter version, called a "finite-one reduction," requires that the converting function maps only finitely many inputs to any single output. These finite-one degrees carve up the many-one degrees into finer slices, and researchers want to understand how this finer structure looks inside each many-one degree.

The central question this paper resolves is: how many finite-one degrees can live inside a single many-one degree? Specifically, can a many-one degree contain exactly two finite-one degrees, or three, or any other specific finite number greater than one? The paper proves that the answer is no. Every many-one degree that corresponds to an unsolvable problem must contain either exactly one finite-one degree or infinitely many of them. There is no middle ground where you get some small but finite collection larger than one.

This result closes a problem that had been partially understood before. Earlier research had shown that for "almost all" problems, in a precise probabilistic sense, the relevant many-one degree contains infinitely many finite-one degrees arranged in a particularly rich way. But that left open whether every single many-one degree of an unsolvable problem had to behave this way, or whether some rare exceptions with only finitely many finite-one degrees could exist beyond the trivial case of exactly one. The new theorem settles this completely, showing the only finite possibility is exactly one, with no exceptions among unsolvable problems.

Read original →