Submission date: 29 April 2012.

Abstract:

We construct the first examples of finitely presented residually finite groups with arbitrarily complicated word problem 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, and give an example of a finitely presented (solvable of class 3) group with NP-complete word problem.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 1204.6506: pdf, ps.