Complete problems for symmetric logspace involving free groups. (English) Zbl 0743.68064

Summary: We show that the Generalized Word Problem for finitely-generated subgroups of Countably-generated free groups with generators of length 2, GWPC(2), is complete for NSYMLOG via logspace reductions. We use N. Immerman’s logical characterization of NSYMLOG as \((FO+\hbox{pos}STC)\), in [SIAM J. Comput. 16, 760-778 (1987; Zbl 0634.68034)].


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
20F05 Generators, relations, and presentations of groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)


Zbl 0634.68034
Full Text: DOI


[1] Avenhaus, J.; Madlener, K., The Nielsen reduction and P-complete problems in free groups, Theoret. comput. sci., 32, 61-76, (1984) · Zbl 0555.20015
[2] Immerman, N., Languages that capture complexity classes, SIAM J. comput., 16, 4, 760-778, (1987) · Zbl 0634.68034
[3] Lewis, H.R.; Papadimitriou, C.H., Symmetric space bounded computation, Theoret. comput. sci., 19, 161-187, (1982) · Zbl 0491.68045
[4] Lipton, R.J.; Zalcstein, Y., Word problems solvable in logspace, J. ACM, 24, 3, 522-526, (1977) · Zbl 0359.68049
[5] Lyndon, R.C.; Schupp, P.E., Combinatorial group theory, (1977), Springer New York · Zbl 0368.20023
[6] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial group theory, (1976), Dover New York
[7] Reif, J., Symmetric complementation, J. ACM, 31, 2, 401-421, (1984) · Zbl 0632.68062
[8] Rotman, J.J., An introduction to the theory of groups, (1984), Allyn & Bacon Newton, MA · Zbl 0576.20001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.