A Question
I have been sick, which means you reduce the throttle, but don't shut down; you hover between rest and work, and try to get out of it at least half ahead, or only half behind, if that makes any sense. In that state, I noticed the comment that appeared in response to the post on Valiant at lance/GASARCH Blog:
Valiant proved the equivalence between Boolean Matrix Multiplication and Context Free Parsing - which was considered a major result - at least in the late 70's. Ref: Valiant, Leslie G. 1975. General context-free recognition in less than cubic time. Journal of Computer and System Sciences, 10:308--315. 11:35 AM, February 18, 2008.
This comment reminded me of a question many have had in their mind for some time: can regular expressions be recognized in sub-quadratic time? In particular, and this may be from the left field, is there a way to show that regular expression recognition encodes matrix multiplication (on some reduced input)? We know that certain simple cases encode integer multiplication, but we need more insights.
Valiant proved the equivalence between Boolean Matrix Multiplication and Context Free Parsing - which was considered a major result - at least in the late 70's. Ref: Valiant, Leslie G. 1975. General context-free recognition in less than cubic time. Journal of Computer and System Sciences, 10:308--315. 11:35 AM, February 18, 2008.
This comment reminded me of a question many have had in their mind for some time: can regular expressions be recognized in sub-quadratic time? In particular, and this may be from the left field, is there a way to show that regular expression recognition encodes matrix multiplication (on some reduced input)? We know that certain simple cases encode integer multiplication, but we need more insights.
posted by metoo at 2:18 AM
2 Comments:
Is it known how to get O(n^3/polylog) time or even this is unknown?
O(n^2) is the standard algorithm from textbooks. I think there are O(n^2/log) time algorithms. So, any encoding of matrix multiplication, if it is true, has to be done on some smaller instances.
Post a Comment
<< Home