Efficient computation in groups and simplicial complexes

Author:
John C. Stillwell

Journal:
Trans. Amer. Math. Soc. **276** (1983), 715-727

MSC:
Primary 03D15; Secondary 03D40, 20F10, 57M05

DOI:
https://doi.org/10.1090/S0002-9947-1983-0688973-8

MathSciNet review:
688973

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Using HNN extensions of the Boone-Britton group, a group is obtained which simulates Turing machine computation in linear space and cubic time. Space in is measured by the length of words, and time by the number of substitutions of defining relators and conjugations by generators required to convert one word to another. The space bound is used to derive a PSPACE-complete problem for a topological model of computation previously used to characterize NP-completeness and RE-completeness.

**1.**William W. Boone,*Certain simple, unsolvable problems of group theory. I*, Nederl. Akad. Wetensch. Proc. Ser. A.**57**(1954), 231–237 = Indag. Math. 16, 231–237 (1954). MR**0066372****[1]**William W. Boone,*The word problem*, Ann. of Math. (2)**70**(1959), 207–265. MR**0179237**, https://doi.org/10.2307/1970103**[2]**John L. Britton,*The word problem*, Ann. of Math. (2)**77**(1963), 16–32. MR**0168633**, https://doi.org/10.2307/1970200**[3]**J. L. Britton,*The word problem for groups*, Proc. London Math. Soc. (3)**8**(1958), 493–506. MR**0125019**, https://doi.org/10.1112/plms/s3-8.4.493**[4]**StÈ§l Aanderaa and Daniel E. Cohen,*Modular machines, the word problem for finitely presented groups and Collins’ theorem*, Word problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), Stud. Logic Foundations Math., vol. 95, North-Holland, Amsterdam-New York, 1980, pp. 1–16. MR**579934****[5]**Michael R. Garey and David S. Johnson,*Computers and intractability*, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences. MR**519066****[6]**G. Higman,*Subgroups of finitely presented groups*, Proc. Roy. Soc. Ser. A**262**(1961), 455–475. MR**0130286****[7]**Graham Higman, B. H. Neumann, and Hanna Neumann,*Embedding theorems for groups*, J. London Math. Soc.**24**(1949), 247–254. MR**0032641**, https://doi.org/10.1112/jlms/s1-24.4.247**[8]**Ralph McKenzie and Richard J. Thompson,*An elementary construction of unsolvable word problems in group theory*, Word problems: decision problems and the Burnside problem in group theory (Conf., Univ. California, Irvine, Calif. 1969; dedicated to Hanna Neumann), Studies in Logic and the Foundations of Math., vol. 71, North-Holland, Amsterdam, 1973, pp. 457–478. MR**0396769****[9]**P. S. Novikov,*Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp*, Trudy Mat. Inst. im. Steklov. no. 44, Izdat. Akad. Nauk SSSR, Moscow, 1955 (Russian). MR**0075197****[10]**Emil L. Post,*Recursive unsolvability of a problem of Thue*, J. Symbolic Logic**12**(1947), 1–11. MR**0020527**, https://doi.org/10.2307/2267170**[11]**Joseph R. Shoenfield,*Mathematical logic*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1967. MR**0225631****[12]**John C. Stillwell,*Isotopy in surface complexes from the computational viewpoint*, Bull. Austral. Math. Soc.**20**(1979), no. 1, 1–6. MR**544363**, https://doi.org/10.1017/S0004972700009047**[13]**John C. Stillwell,*Unsolvability of the knot problem for surface complexes*, Bull. Austral. Math. Soc.**20**(1979), no. 1, 131–137. MR**544373**, https://doi.org/10.1017/S000497270000914X**[14]**John Stillwell,*The word problem and the isomorphism problem for groups*, Bull. Amer. Math. Soc. (N.S.)**6**(1982), no. 1, 33–56. MR**634433**, https://doi.org/10.1090/S0273-0979-1982-14963-1**[15]**B. A. Trahtenbrot,*The complexity of reduction algorithms in Novikov-Boone constructions.*, Algebra i Logika**8**(1969), 93–128 (Russian). MR**0285389****[16]**M. K. Valiev,*The complexity of the word problem for finitely presented groups*, Algebra i Logika**8**(1969), 5–43 (Russian). MR**0306334****[17]**M. K. Valiev,*On polynomial reducibility of the word problem under embedding of recursively presented groups in finitely presented groups*, Mathematical foundations of computer science 1975 (Fourth Sympos., Mariánské Lázně, 1975) Springer, Berlin, 1975, pp. 432–438. Lecture Notes in Comput. Sci., Vol. 32. MR**0412287**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
03D15,
03D40,
20F10,
57M05

Retrieve articles in all journals with MSC: 03D15, 03D40, 20F10, 57M05

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1983-0688973-8

Keywords:
Word problem for groups,
Turing machines,
two-dimensional complexes,
polynomial time computation

Article copyright:
© Copyright 1983
American Mathematical Society