Computable structure theory asks which mathematical objects can be described by algorithms and how much computational power is needed to work with them. One useful construction in this area is the "cohesive power," which takes a computable mathematical structure and a special infinite set called a cohesive set, and produces a new, typically more complex structure. Cohesive sets are infinite sets that cannot be meaningfully split into two infinite pieces by any computable procedure. The cohesive power construction is interesting because it can turn simple, computable structures into ones that encode hard computational problems, and this paper investigates exactly how hard those encoded problems can be.
The authors construct two specific examples that reveal the limits and strengths of cohesive powers. First, they build a computable graph such that taking its cohesive power always produces a structure of a very specific and high computational complexity, equivalent to solving the "double halting problem," a canonical benchmark of hardness in computability theory. This is a tight result: that level of complexity is both sufficient and necessary to describe the resulting structure. Second, they build a computable linear ordering, which is essentially a way of arranging objects in a sequence, such that no matter which cohesive set you use to form the cohesive power, the resulting structure can never be described by any algorithm at all.
These results echo a classical theorem by Tennenbaum from the 1960s, which showed that nonstandard models of arithmetic, meaning mathematical systems that satisfy the axioms of arithmetic but contain "extra" elements beyond the usual whole numbers, can never be computably presented. The paper's results show that cohesive powers behave similarly: they can force structures to be computationally intractable in ways that mirror Tennenbaum's original insight. Together the two constructions sharply characterize what cohesive powers can encode, showing they can be tuned to produce structures of precise and high complexity.