Reductions and functors from problems to word problems

Jean Camille Birget

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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

Original languageEnglish (US)
Pages (from-to)81-104
Number of pages24
JournalTheoretical Computer Science
Volume237
Issue number1-2
DOIs
StatePublished - Apr 28 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Complexity
  • Functors
  • Reductions
  • Word problem

Fingerprint

Dive into the research topics of 'Reductions and functors from problems to word problems'. Together they form a unique fingerprint.

Cite this