The quadratic-time word problem conjecture for special monoids with virtually free units
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.