Reductions and functors from problems to word problems (Q1566706)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reductions and functors from problems to word problems |
scientific article |
Statements
Reductions and functors from problems to word problems (English)
0 references
4 June 2000
0 references
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).
0 references
Word problem
0 references
Complexity
0 references
Reductions
0 references
Functors
0 references