Математик: ИИ-система решила задачу, которую считали нерешаемой
The recently proposed o(n log n) integer multiplication algorithm [pdf]
Дэвид Харви из UNSW разбирает недавно предложенный алгоритм умножения целых чисел со сложностью o(n log n) — ниже считавшегося оптимальным предела O(n log n). Он не читал статьи, а попросил Claude Fable 5.1 объяснить их, и пришёл к выводу, что результат правдоподобен. Харви также предупреждает: люди-авторы математических работ могут скоро перестать восприниматься всерьёз, как студенты, сдающие письменные работы.
Я сомневаюсь, что люди ещё долго смогут восприниматься всерьёз как авторы математических исследовательских работ — по той же причине, по которой мы больше не принимаем письменные работы у студентов.
- jdb1729
> Было бы хорошо иметь формализованное доказательство результата o(n log n), например, в Lean. Насколько я могу судить, его пока не существует.
Результат полностью формализован в Lean мной и @platypii (на машине TM2 из Mathlib), с постоянными улучшениями показателя степени (сейчас 1-2^-14.38): https://github.com/platypii/integer-mult-bounds-lean
Приглашаем к участию!
- Kapura
> Я на самом деле не читал статью. Более того, есть три тесно связанные статьи [TC26a], [TC26b], [TC26c], и я не читал ни одну из них. Я пытался, но вскоре сдался. Сборник математических выкладок, похоже, не силён в изложении. Вместо этого я попросил Fable объяснить мне [TC26a]. Fable, кажется, понимает аргументацию и считает её правильной.
это не кажется здоровой ситуацией
- kenferry
> Есть ещё один аспект ситуации, который я хотел бы подчеркнуть. После двух недель очень
упорной работы я смог понять лишь малую часть [TC26a]. Когда я спрашиваю Fable о
статье, кажется, что она читает и понимает всё целиком всего за несколько минут, даже
начиная с чистого контекста. Я знаю, что некоторым читателям может быть некомфортна моя антропоморфная
терминология, но я считаю, что «понимать» — точное слово, в том смысле, что LLM, похоже, способна
правильно и ясно отвечать на всевозможные вопросы о статье, включая некоторые очень
каверзные технические детали. Именно так я бы определил, что человеческий коллега «понял»
что-то. Эта пропасть между «скоростью мысли» человека и LLM, по меньшей мере, тревожит.
Это очень странно, потому что это совершенно не соответствует моему опыту с этими системами. Да, они обычно ЗВУЧАТ уверенно, но код (скажем), который мне трудно понять, обычно труден для понимания и машине, и хотя она более неутомима, чем я, она не умнее.
Этот математик находится в очень хорошей позиции, чтобы оценить, понимает ли Fable или нет, но это странно и противоречит моему опыту.
- jdb1729
> Новый результат напрямую не влечёт новых границ сложности для умножения многочленов над фиксированным конечным полем, скажем, умножения в F2[x]. Лучший известный результат для этой задачи — алгоритм, который умножает многочлены степени n за время O(n log n 4^log*(n)) [HvdH19].
Мы с @platypii получили доказательство в Lean того же улучшения для DFT над конечными полями простого порядка (что даёт умножение многочленов через теорему о свёртке): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
- flebron
Обратите внимание, в данном случае в заголовке написано «O(n log n)», но важная часть в том, что это «o(n log n)», а не просто «O(n log n)». Первое — строгое подмножество второго. Мы уже знали, как умножать два n-битных целых числа за время O(n log n) с помощью FFT.
- CH-Abhinav
Новичок здесь, но как это помогает в целом? В большинстве случаев мы используем GEMM вместо Strassen, хотя временная сложность ниже. Просто спросите, я ничего не знаю :)
- kleiba2
Интересно, что ИИ, видимо, не пишет статьи для людей: даже экспертам трудно их понять. Но другие ИИ понимают. Так что ИИ в основном пишет статьи для других ИИ.
- yaoke259
Отличная статья и введение от собрата-сиднейца, не мог оторваться! Как человек, не являющийся математическим гением, я пропустил технические детали мимо ушей, но текст, позволивший мне глубоко сопереживать людям в этой области, был очень познавательным. Я никогда не осознавал, насколько важным был этот математический прорыв и как сильно он встряхнул область. Полагаю, мы все просто пытаемся разобраться в этой штуке под названием «интеллект по требованию» вместе.