My question is about the complexity of the word problem in the free group $F_2=\langle a,b\rangle$. Formally, we define the problem

$\textsf{WPFree}=\{ w\in\{a^{\pm 1},b^{\pm 1}\}^{*}\,|\, \mbox{$w$ reduces to the empty word} \}$

It is written everywhere that the complexity is linear. Indeed, if we consider Turing machines with several tapes, it is easy to solve the problem in linear time. However, I don't see how to construct a standard Turing machine with one tape solving this problem in linear time.

Question: Is $\textsf{WPFree}\in \textsf{DTIME}(n)$?


1 Answer 1


The answer is the following: $$ \textrm{WPFree}\in \textrm{DTIME}(n^2) \mbox{ and } \textrm{WPFree}\not\in \textrm{DTIME}(o(n^2)). $$ The first claim holds because every problem, that can be solved in linear time by a multitape Turing machine, can be solved in quadratic time on a single tape. The second claim is more involved, but basically follows the standard proof that palindromes cannot be regonized in $o(n^2)$ time on a single tape.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .