Circuits, the groups of Richard Thompson, and coNP-completeness

Research output: Contribution to journalArticle

12 Scopus citations

Abstract

We construct a finitely presented group with coNP-complete word problem, and a finitely generated simple group with coNP-complete word problem. These groups are represented as Thompson groups, hence as partial transformation groups of strings. The proof provides a simulation of combinational circuits by elements of the Thompson - Higman group G3,1.

Original languageEnglish (US)
Pages (from-to)35-90
Number of pages56
JournalInternational Journal of Algebra and Computation
Volume16
Issue number1
DOIs
StatePublished - Feb 1 2006

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Groups
  • Word problem
  • coNP-completeness

Fingerprint Dive into the research topics of 'Circuits, the groups of Richard Thompson, and coNP-completeness'. Together they form a unique fingerprint.

  • Cite this