Сама задача оценки экспоненты матричного умножения по уровню вовлечённости напоминает теорему Ферма. Все верят, что в итоге в качестве оценки будет получена константа 2. Жаль, пока никто не может этого доказать.
Наверное каждый третий математик, который имеет отношение к вычислительной алгебре, когда-то брался за эту задачу. Есть математики, которые положили жизнь на решение этой задачи, и не смогли получить новой оценки.
...
Кстати, по поводу математиков, положивших жизнь. Есть репорт Джеймса Ива. Он два года назад опубликовал свои промежуточные результаты с оценкой n^{2+o(1)}. И вскоре после этого умер. В самом репорте есть комментарий Дональда Кнута, который пишет, что в каком-то месте не понял.
--
http://habrahabr.ru/blogs/algorithm/1338...
add comment
recommend
bookmark
subscribe