Reductions and functors from problems to word problems

AbstractWe introduce reductions of problems to word problems of finitely generated semigroups and groups, with special properties.(1) Complexity properties: The reductions are computable in linear time, and they reduce problems to word problems with approximately the same time complexity. For groups, the constructions use small-cancellation theory.(2) Algebraic properties: We also associate semigroups and groups with reduction functions, in such a way that composition of reduction functions corresponds to the free product with amalgamation. Moreover, we make the reductions (from problems to word problems) functorial. For this, we reformulate problem classes as categories (e.g., NP can be viewed as the category whose objects are the languages in NP, and whose arrows are all polynomial-time one-to-one reductions)