The quadratic-time word problem conjecture for special monoids with virtually free units
The quadratic-time word problem conjecture for special monoids with virtually free units
Let be a finitely presented special monoid, generated by , with virtually free group of units. For inputs , write . Quadratic-time word problem conjecture. The word problem for is decidable in time. Matrix multiplication has the lower bound , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.