The computational complexity of recognising embeddings in finitely presented groups

Details The computational complexity of recognising embeddings in finitely presented groups The computational complexity of recognising embeddings in finitely presented groups

2011-07-07

arxiv.org/abs/1107.1489v1

Mathematics

Group Theory

8 pages

Scientific paper

We extend a result by Lempp that recognising torsion-freeness for finitely presented groups is $\Pi^{0}_{2}$-complete; we show that the problem of recognising embeddings of finitely presented groups is at least $\Pi^{0}_{2}$-hard, $\Sigma^{0}_{2}$-hard, and lies in $\Sigma^{0}_{3}$. We conjecture that this problem is indeed $\Sigma^{0}_{3}$-complete. We use our constructions to form a universal finitely presented torsion-free group.

Affiliated with

Also associated with

No associations

Rating

The computational complexity of recognising embeddings in finitely presented groups 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 The computational complexity of recognising embeddings in finitely presented groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The computational complexity of recognising embeddings in finitely presented groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-417597