Algorithmically complex residually finite groups
- Resource Type
- Working Paper
- Authors
- Kharlampovich, O.; Myasnikov, A.; Sapir, M.
- Source
- Subject
- Mathematics - Group Theory
Mathematics - Logic
- Language
We construct the first examples of an algorithmically complex finitely presented residually finite groups and first examples of finitely presented residually finite groups with arbitrarily large (recursive) Dehn function and depth function. The groups are solvable of class 3. We also prove that the universal theory of finite solvable of class 3 groups is undecidable.
Comment: 32 pages; v2: misprints fixed; v3: removed the result about NP-completeness. The input language of any Minsky machine is sparse, so one cannot use our construction to build a finitely presented group with NP-complete word problem. We thank Markus Lohrey and Jean-Camille Birget for that observation. v4: Introduction is expanded, proofs are clarified. v5: Some corrections are made