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

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

2003-10-21

arxiv.org/abs/math/0310335v1

Mathematics

Group Theory

73 pages

Scientific paper

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 G_{3,1}.

Affiliated with

Also associated with

No associations

Rating

Circuits, coNP-completeness, and the groups of Richard Thompson does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Circuits, coNP-completeness, and the groups of Richard Thompson, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuits, coNP-completeness, and the groups of Richard Thompson will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-510180