Задача 3SUM решена быстрее, чем за O(N²) — а именно за O(N¹·⁹⁹⁹²). Без нейронок не обошлось
Habr ·
5 октября американские исследователи Вирджиния Василевска-Уильямс, известная своими быстрыми (и безумно сложными) алгоритмами перемножения матриц за вместо и её бывший аспирант Джош Алман опубликовали препринт на arxiv.org , демонстрирующий алгоритм решения задачи 3SUM за . Это знаковое событие в узких кругах. Во-первых, раньше предполагалось, что решить эту задачу быстрее, чем за , невозможно. Во-вторых, вместе с ней наконец решилась быстрее, чем за , задача нахождения кратчайших путей между любыми парами вершин в графе (All-Pairs Shortest Paths, APSP) — по-настоящему практическая задача вычислительной геометрии. В-третьих, мало того, что корректность работы проверяла закрытая модель Anthropic — авторы также утверждают, что Claude нашёл изначальный алгоритм , после чего учёные осознали и улучшили его. В этой новости я очень кратко перескажу долгий путь, который привёл к этому открытию, и опишу роль LLM в финале этого пути. Читать далее
5 октября американские исследователи Вирджиния Василевска-Уильямс, известная своими быстрыми (и безумно сложными) алгоритмами перемножения матриц за вместо и её бывший аспирант Джош Алман опубликовали препринт на arxiv.org , демонстрирующий алгоритм решения задачи 3SUM за . Это знаковое событие в узких кругах. Во-первых, раньше предполагалось, что решить эту задачу быстрее, чем за , невозможно. Во-вторых, вместе с ней наконец решилась быстрее, чем за , задача нахождения кратчайших путей между любыми парами вершин в графе (All-Pairs Shortest Paths, APSP) — по-настоящему практическая задача вычислительной геометрии. В-третьих, мало того, что корректность работы проверяла закрытая модель Anthropic — авторы также утверждают, что Claude нашёл изначальный алгоритм , после чего учёные осознали и улучшили его. В этой новости я очень кратко перескажу долгий путь, который привёл к этому открытию, и опишу роль LLM в финале этого пути. Читать далее