The quadratic-time word problem conjecture for special monoids with virtually free units

Let MM be a finitely presented special monoid, generated by AA, with virtually free group of units. For inputs u,vAu,v\in A^*, write n=u+vn=|u|+|v|. Quadratic-time word problem conjecture. The word problem for MM is decidable in O(n2)O(n^2) time. Matrix multiplication has the lower bound O(n2)O(n^2), so this conjecture would make the current reduction-based bound optimal. It is motivated by the conjectured optimal quadratic-time algorithm for matrix multiplication.

Sources & referencesView supporting material

Primary source

Carl-Fredrik Nyberg-Brodda, “On the Word Problem for Special Monoids”, arXiv:2011.09466 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.