Sign in
Back
CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS
Journal article   Peer reviewed

CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS

JEAN-CAMILLE Birget
International journal of algebra and computation, Vol.16(1), pp.35-90
02/2006
DOI: https://doi.org/10.1142/S0218196706002822

Abstract

coNP-completeness Groups word problem
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.

Metrics

8 Record Views
14 Times Cited - Web of Science

Details