Efficient computation in groups and simplicial complexes

Stillwell, John C.

doi:10.1090/S0002-9947-1983-0688973-8

Efficient computation in groups and simplicial complexes
HTML articles powered by AMS MathViewer

by John C. Stillwell PDF

Trans. Amer. Math. Soc. 276 (1983), 715-727 Request permission

Abstract:

Using HNN extensions of the Boone-Britton group, a group $E$ is obtained which simulates Turing machine computation in linear space and cubic time. Space in $E$ 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.

References

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
William W. Boone, The word problem, Ann. of Math. (2) 70 (1959), 207–265. MR 179237, DOI 10.2307/1970103
John L. Britton, The word problem, Ann. of Math. (2) 77 (1963), 16–32. MR 168633, DOI 10.2307/1970200
J. L. Britton, The word problem for groups, Proc. London Math. Soc. (3) 8 (1958), 493–506. MR 125019, DOI 10.1112/plms/s3-8.4.493
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), Studies in Logic and the Foundations of Mathematics, vol. 95, North-Holland, Amsterdam-New York, 1980, pp. 1–16. MR 579934
Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
G. Higman, Subgroups of finitely presented groups, Proc. Roy. Soc. London Ser. A 262 (1961), 455–475. MR 130286, DOI 10.1098/rspa.1961.0132
Graham Higman, B. H. Neumann, and Hanna Neumann, Embedding theorems for groups, J. London Math. Soc. 24 (1949), 247–254. MR 32641, DOI 10.1112/jlms/s1-24.4.247
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, DOI 10.1016/0003-4916(72)90140-6
P. S. Novikov, Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp, Izdat. Akad. Nauk SSSR, Moscow, 1955 (Russian). Trudy Mat. Inst. Steklov. no. 44. MR 0075197
Emil L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1–11. MR 20527, DOI 10.2307/2267170
Joseph R. Shoenfield, Mathematical logic, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1967. MR 0225631
John C. Stillwell, Isotopy in surface complexes from the computational viewpoint, Bull. Austral. Math. Soc. 20 (1979), no. 1, 1–6. MR 544363, DOI 10.1017/S0004972700009047
John C. Stillwell, Unsolvability of the knot problem for surface complexes, Bull. Austral. Math. Soc. 20 (1979), no. 1, 131–137. MR 544373, DOI 10.1017/S000497270000914X
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, DOI 10.1090/S0273-0979-1982-14963-1
B. A. Trahtenbrot, The complexity of reduction algorithms in Novikov-Boone constructions. , Algebra i Logika 8 (1969), 93–128 (Russian). MR 0285389
M. K. Valiev, The complexity of the word problem for finitely presented groups, Algebra i Logika 8 (1969), 5–43 (Russian). MR 0306334
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) Lecture Notes in Comput. Sci., Vol. 32, Springer, Berlin, 1975, pp. 432–438. MR 0412287