3 ms·
It's not a tight lower bound unless it's proven that no greater value could be a lower bound, and that's very much an open problem if I understand correctly.
by cwillu 3y ago
It's not a tight lower bound unless it's proven that no greater value could be a lower bound, and that's very much an open problem if I understand correctly.
- Asraelite 3y agoWhat's the difference between doing that and just straight up proving what the exact value is?
- Someone 3y agoIt cannot be harder, and could be a lot easier. Lots (well, relatively lots; this isn’t a research area with millions of practitioners) of people must have been looking at that problem ever since Strassen showed the exact value is less than 3 in 1969 (https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm), and there hasn’t been progress on moving that needle, so I doubt it’s even remotely easy, though.
- seanhunter 3y agoDepending on the nature of the problem and the proof technique, sometimes it can be (from a little to much) easier to prove something is no greater than or no less than a certain bound than proving what exactly it is. For example it's trivial to prove using triangles that the square root of two is somewhere between 7/5 and 3/2 but proving exactly the value of root two is quite a lot harder.
- pletnes 3y agoIndeed - a classic «upping the game» is to prove two bounds, then determine an exact value because you somehow get the bounds to intersect. https://en.wikipedia.org/wiki/Squeeze_theorem?wprov=sfti1 https://en.wikipedia.org/wiki/Squeeze_theorem?wprov=sfti1
- burnished 3y agoHell yeah, squeeze theorem! I was so enchanted when I first learned this one that everyone I knew also learned about the squeeze theorem. Sorry, nothing substantial to add, I just got excited about it again
- layer8 3y agoTo prove the exact value, you generally have to provide an algorithm that (provably) fulfills that value, and also prove that no other algorithm can possibly do better