Odifreddi’s c.e. truth-table versus many-one degree question

Does every computably enumerable truth-table degree contain a computably enumerable irreducible many-one degree? The target is a c.e. degree with no such representative.

Why it matters and what counts as progress

Why it matters: It tests a computably enumerable strengthening of a relationship between two notions of reducibility.

What counts as progress: Construct a c.e. truth-table degree with no c.e. irreducible many-one representative, or identify a restricted class where such representatives exist.

How the problem developed

1969 · Partial result [1]
Carl G. Jockusch Jr. Showed that every c.e. truth-table degree contains an irreducible many-one degree, without requiring that degree itself to be c.e.
1981 · Open problem [2]
Piergiorgio Odifreddi Explicitly asked whether every c.e. tt-degree contains a c.e. m-degree consisting of a single 1-degree.
4 May 2026 · Counterexample [3]
Patrizio Cintioli Gave a negative answer by constructing a c.e. tt-degree containing no c.e. irreducible m-degree; the result makes Jockusch’s weaker theorem sharp.

AI contribution

A Computably Enumerable tt-Degree Without Computably Enumerable Irreducible m-Degrees

Patrizio Cintioli

Some computably enumerable truth-table degree contains no computably enumerable irreducible many-one degree. Cintioli derives the example using Degtev’s c.e. semirecursive set with rigid complement and the fact that its simple-set representatives cannot be irreducible cylinders.

AI involvementAI-centered

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull