TY - JOUR

T1 - Reductions and functors from problems to word problems

AU - Birget, Jean Camille

N1 - Funding Information:
(Supported in part by NSF grant DMS-9203981. Part of this work was done while the author visited the LITP/LIAFA, U. of Paris 7. ∗E-mail address: birget@cse.unl.edu (J.-C. Birget)

PY - 2000/4/28

Y1 - 2000/4/28

N2 - We 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).

AB - We 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).

KW - Complexity

KW - Functors

KW - Reductions

KW - Word problem

UR - http://www.scopus.com/inward/record.url?scp=0347997364&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347997364&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(98)00131-5

DO - 10.1016/S0304-3975(98)00131-5

M3 - Article

AN - SCOPUS:0347997364

SN - 0304-3975

VL - 237

SP - 81

EP - 104

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -