Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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 Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. W. W. Boone, Certain simple unsolvable problems of group theory. I-VI, Nederl. Akad. Wetensch. Indag. Math. 57 (1954), 231-237, 492-497; 58 (1955), 252-256, 571-577; 60 (1957), 22-27, 227-232. MR 0066372 (16:564d)
  • [1] -, The word problem, Ann. of Math. (2) 70 (1959), 207-265. MR 0179237 (31:3485)
  • [2] J. L. Britton, The word problem, Ann. of Math. (2) 77 (1963), 16-32. MR 0168633 (29:5891)
  • [3] -, The word problem for groups, Proc. London Math. Soc. 8 (1958), 493-506. MR 0125019 (23:A2326)
  • [4] D. E. Cohen and S. Aanderaa, Módular machines, the word problem for finitely presented groups, and Collins' theorem, Word Problems. II (S. I. Adian, W. W. Boone and G. Higman, editors), North-Holland, Amsterdam, 1980, pp. 1-16. MR 579934 (81m:20048)
  • [5] M. R. Garey and D. S. Johnson, Computers and intractibility, Freeman, San Francisco, Calif., 1979. MR 519066 (80g:68056)
  • [6] G. Higman, Subgroups of finitely presented groups, Proc. Roy. Soc. London Ser. A 262 (1961), 455-475. MR 0130286 (24:A152)
  • [7] G. Higman, B. H. Neumann and H. Neumann, Embedding theorems for groups, J. London Math. Soc. 24 (1949), 247-254. MR 0032641 (11:322d)
  • [8] R. McKenzie and R. J. Thompson, An elementary construction of unsolvable word problems in group theory, Word Problems (W. W. Boone, F. B. Cannonito and R. C. Lyndon, editors), North-Holland, Amsterdam, 1973, pp. 457-478. MR 0396769 (53:629)
  • [9] P. S. Novikov, On the algorithmic unsolvability of the word problem in group theory, Trudy Mat. Inst. Steklov 44 (1955), (Russian) MR 0075197 (17:706b)
  • [10] E. L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1-11. MR 0020527 (8:558b)
  • [11] J. R. Shoenfield, Mathematical logic, Addison-Wesley, Reading, Mass., 1967. MR 0225631 (37:1224)
  • [12] J. C. Stillwell, Isotopy in surface complexes from the computational viewpoint, Bull. Austral. Math. Soc. 20 (1979), 1-6. MR 544363 (80j:03059)
  • [13] -, Unsolvability of the knot problem for surface complexes, Bull. Austral. Math. Soc. 20 (1979), 131-137. MR 544373 (80j:03060)
  • [14] -, The word problem and the isomorphism problem for groups, Bull. Amer. Math. Soc. 6 (1982), 33-56. MR 634433 (82m:20039)
  • [15] B. A. Trakhtenbrot, On the complexity of reduction algorithms in Novikov-Boone constructions, Algebra and Logic 8 (1969), 93-128. MR 0285389 (44:2608)
  • [16] M. K. Valiev, On the complexity of the identity problem for finitely defined groups, Algebra and Logic 8 (1969), 5-43. MR 0306334 (46:5460)
  • [17] -, On polynomial reducibiliity of word problem under embedding of recursively presented groups in finitely presented groups, Lecture Notes in Computer Science, vol. 32, Springer-Verlag, Berlin and New York, 1975, pp. 432-438. MR 0412287 (54:413)

Similar Articles

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

American Mathematical Society