A resource-bounded Kolmogorov complexity measure for polynomial-time reductions

This article introduces a new way to measure the complexity of polynomial-time reductions,the transformations used to compare computational problems. While reductions are central to complexity theory, they are usually treated simply as arrows between problems; their internal structure is rarely examined. This paper proposes treating reductions themselves as objects of study. The main contribution is a descriptive complexity measure called κₙ^{poly}(R). For a reduction R and a size bound n, this measures the length of the shortest program that correctly computes R on all inputs of length at most n, with the crucial requirement that the program must run in polynomial time on every input (not just those of length ≤ n). This uniform time bound is essential: without it, the measure would collapse to ordinary Kolmogorov complexity of a finite function, which is trivial. The paper establishes three fundamental properties of this measure. First, it is invariant under the choice of universal Turing machine up to an additive constant. Second, it satisfies a composition theorem: when reductions are composed, their descriptive complexity adds in a way that accounts for possible growth in intermediate outputs. Third, the identity reduction has constant complexity. The authors also prove that reductions can have arbitrarily high descriptive complexity,specifically, for each n there exists a reduction with κₙ^{poly}(R) at least 2ⁿ. This exponential lower bound shows the measure is nontrivial. Based on how κₙ^{poly}(R) grows with n, the paper defines three complexity classes for reductions: PolyRed (logarithmic growth), ExpRed (polynomial growth), and RandRed (super-polylogarithmic growth). The exponential lower bound shows RandRed is nonempty. Finally, the article presents several open problems connecting this framework to longstanding questions in complexity theory: whether all NP-complete problems are connected by logarithmically describable reductions (related to the Berman-Hartmanis conjecture), whether there exists a "descriptively universal" NP-complete problem, the relationship between descriptive complexity and circuit size, whether this measure might evade the natural proofs barrier, and whether there is a notion of completeness within reduction complexity classes themselves.