4 ms·
I'm confused by this argument. To show that > if CFG parsing was n^2, so is boolean matrix multiplication wouldn't you need to show that any boolean matrix mu
by moefh 10y ago
I'm confused by this argument. To show that
> if CFG parsing was n^2, so is boolean matrix multiplication
wouldn't you need to show that any boolean matrix multiplication can be turned into CFG parsing (and not the converse)?
- deleted 10y ago[deleted]
- justinpombrio 10y agoGreat question, I just learned something. A boolean matrix multiplication problem can be turned into a CFG problem. Therefore, an algorithm that solves CFG problems can be turned into an algorithm that solves boolean matrix multiplication.
- DannyBee 10y agoSorry, yes, i deleted a line accidentally, but it turns out you can show both directions, and to prove a tight bound, you need to show they reduce to each other without changing the complexity class.