Premium
Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
Author(s) -
Cohen Daniel E.,
Madlener Klaus,
Otto Friedrich
Publication year - 1993
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19930390117
Subject(s) - turing machine , word problem (mathematics education) , mathematics , complexity class , word (group theory) , kolmogorov complexity , mathematical proof , time hierarchy theorem , time complexity , group (periodic table) , computational complexity theory , natural number , algorithm , discrete mathematics , universal turing machine , theoretical computer science , computer science , arithmetic , chemistry , geometry , organic chemistry , computation
Abstract A pseudo‐natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo‐natural algorithm is arbitrarily more complicated than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo‐natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented group G from a Turing machine T such that the intrinsic complexity of the word problem for G reflects the complexity of the halting problem of T , while the derivational complexity of the word problem for G reflects the runtime complexity of T. The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40, 20F10.