2/2. продолжение. начало тут.

🧮 Сложность по Тьюрингу (асимптотическая/комбинаторная сложность)
Не будем забывать и об этом виде сложности, которая определяется в терминах машины Тьюринга. В этом контексте мы говорим о вычислительной сложности задачи, то есть о том, сколько ресурсов (время, память) нужно для решения задачи с помощью алгоритма.

Пример:

🎯 Число π — кажется, что оно абсолютно хаотичное: 3.1415926535… Цифры «равномерно раскиданы» (хотя это не доказано).
Энтропия — высокая, потому что предсказать, какие цифры пойдут дальше, сложно. Но! Это не случайность.
π можно сгенерировать по формуле, и мы знаем, как извлечь нужные цифры. Тут энтропия высокая, а Колмогоровская сложность низкая.

💡 Вывод:

📉 Энтропия — когда не знаешь, что дальше.
📦 Колмогоровская сложность — когда даже зная, не можешь объяснить проще.
🧮Тьюринг - а хватит ли нам ресурсов вселенной, шобы вообще вычислить?

📌 В следующий раз поговорим о том, как нейросети справляются с разными задачами и как они используют концепции сложности!

#LLM #Transformer #Complexity

@easy_about_complex

1/2

Когда кот — не просто мурлыка, а соавтор научной статьи

В 1975 году в престижном журнале Physical Review Letters вышла статья "Two-, Three-, and Four-Atom Exchange Effects in bcc ³He", оказавшая значительное влияние на науку. Под ней стояли два имени: Джек Хезерингтон и... Ф.Д.К. Уиллард.

На первый взгляд — ничего подозрительного...

2/2 Продолжение. Начало тут

Но, как выяснилось, одним из «авторов» оказался кот по кличке Честер. 😺

Дело в том, что Хезерингтон написал статью от первого лица множественного числа — «мы», «наш». Когда же редактор напомнил, что он числится как единственный автор, Джек, будучи человеком практичным, не стал перепечатывать весь текст. Ведь это были 70-е, а на печатных машинках не существовало волшебной функции «найти и заменить». Вместо этого он просто приписал в соавторы своего кота. Причём под изящным псевдонимом: F.D.C. Willard — от Felis domesticus Chester Willard. Шах и мат, грамматика.

Когда научное сообщество узнало об этом пушистом физике, кота даже пригласили «присоединиться» к кафедре на full time. К счастью, он не возражал. Главное — не трогайте его лазерную указку.

#Physics #Cats #НастроениеСреды

@easy_about_complex

1/2

🚀 Свежая продвижка в решении 6-й проблемы Гильберта 125 лет спустя — или что такое математическая строгость

Шестая проблема Гильберта — одна из 🧠 23 знаменитых математических задач, сформулированных Давидом Гильбертом в 1900 году на Международном математическом конгрессе в Париже.

📌 Гильберт поставил цель:

"Математическое обоснование тех наук, где математика играет важную роль, прежде всего физики, особенно аксиоматизация тех разделов физики, где господствует вероятностный и статистический подход."

🔬 Основной акцент- аксиоматизация физики, особенно:
- механики (включая статистическую),
- кинетической теории газов,
- теории вероятностей.

2/2. продолжение. начало тут.

🤔 В чём суть и сложность?
На рубеже XIX–XX веков у физиков были три уровня описания жидкостей и газов:

⚙️ Ньютоновская механика — точные уравнения движения для каждой молекулы.

🎲 Кинетическая теория Больцмана — вероятностные распределения частиц по скоростям.

🌊 Уравнения Эйлера / Навье–Стокса — конкретные значения плотности, давления, скорости в каждой точке.

Но вот проблема: описывать каждую молекулу по Ньютону — невозможно (их триллионы 😵). Больцман предложил статистический подход: описывать поведение газа не через каждую частицу, а через вероятностную плотность. Но и это приближение. В реальных инженерных задачах мы ещё сильнее упрощаем — используем уравнения Эйлера или Навье-Стокса, чтобы напрямую считать плотность, давление, скорость.

📉 Проблема в том, что все эти переходы — от микромира к макромиру — до недавнего времени оставались на уровне физической интуиции. Мы как бы «выводим» макроуравнения Эйлера и Навье-Стокса из Больцмана, а Больцмана из Ньютона — но без строгих математических гарантий.

🧩 Чтобы сделать всё по-настоящему строго, нужно:
-оценить погрешность между моделями,
-доказать существование решений на каждом уровне,
-и показать, что они действительно сходятся при предельных переходах.

📚 В этом и суть 6-й проблемы: построить строгий математический мост между механикой Ньютона, статистикой Больцмана и гидродинамикой Эйлера - от микроскопического молекулярного уровня к макроскопическому поведению жидкостей и газов в реальном мире.

💥 И вот, спустя 125 лет, в работе Yu Deng, Zaher Hani и Xiao Ma (2025) arXiv:2503.01800
эта программа, кажется, частично(!) реализована строго математически.

Однако, это лишь препринт! Работа находится в проверке!

P.S. вот тут тоже можно почитать.

#Physics #Math #Hilbert #Hilbert6 #Gasdynamics #Euler #NavierStokes #Newton #Boltsman

@easy_about_complex

Ну и немного сексуальных и развратных намёков. Весна же.

Кто не понял, поставьте 👎

Кто понял, поставьте 👍

Кто смог взять интеграл, но всё равно не понял, поставьте 😇

Кто не смог взять интеграл, но понял, поставьте 😈

#НастроениеПятницы #ПошлыйЮмор

@easy_about_complex

📐 Интегралы, которые невозможно выразить в элементарных функциях

После этого поста стало очевидно, что дорогие читатели этого канала очень любят интегралы.

А вот знаете ли вы, что далеко не все интегралы можно выразить через "обычные" функции вроде синуса, экспоненты или логарифма? Например, классический интеграл

∫𝑒^{−𝑥^2}𝑑𝑥

не имеет выражения через элементарные функции. Его значение задаётся через специальную функцию — ошибку Гаусса (erf).

🔍 Это открытие уходит к работам Жозефа Лиувилля в 1830-х годах. Он доказал теорему существования первообразной в элементарных функциях для определённых видов подинтегральной функции. Но нам же мало знать, что интеграл можно взять? Мы хотим его вычислить алгоритмически!

🧠 В 1969 году Роберт Риш разработал алгоритм (ныне известный как алгоритм Риша), который позволяет автоматически определить, можно ли взять интеграл в элементарных функциях. Этот алгоритм лёг в основу современных систем компьютерной алгебры: Mathematica, Maple, Maxima.

📚 Среди других ключевых работ:
– Бронштейн (1997) — систематизация алгоритмических методов
– Барри Трейгер (1984) — интегралы от алгебраических функций
– Теория "fewnomials" Хованского — на стыке алгебры и анализа

💡 Примеры неэлементарных интегралов:
– ∫sin⁡(𝑥^2)𝑑𝑥
- ∫sin(𝑥)/𝑥𝑑𝑥
- ∫sqrt(1+𝑥^3)𝑑𝑥

Такие выражения требуют специальных функций — от Bessel до эллиптических, и создают мост между алгеброй, анализом и математической физикой.

✳️ Вывод: даже простые на вид интегралы могут скрывать глубокие слои математической теории.

#ODE #ComputerAlgebra #Computability #Algorithms

@easy_about_complex

🔥 Напомню, что следующий лайв-стрим — в воскресенье 11.05.2025! Не пропустите!

На этот раз предварительно планируем разобрать темы:

1️⃣ Математика и ИИ — введение в теорию вычислимости и сложности вычислений + обзор результатов о вычислительной мощности искусственных нейронных сетей (см. тут и тут).

2️⃣ Математика и биология — введение в нейронауку и обсуждение книги Peter Dayan "Theoretical Neuroscience".

3️⃣ Философия - oткрытая дискуссия и дебаты.

🚀 Более подробный/окончательный анонс скоро появится здесь и в канале Hidden_heuristic!

Оставайтесь на связи и готовьте вопросы!

#LiveStream

@easy_about_complex

Немного физики на вечер

Даже в полной пустоте что-то происходит.
С точки зрения квантовой физики, вакуум — это не просто "ничего", а пространство, наполненное энергией. В нём постоянно рождаются и тут же исчезают так называемые виртуальные частицы. Это крошечные всплески энергии, которые не живут и миллисекунды, но всё же существуют. Это явление называется квантовыми флуктуациями.

Учёные уже умеют наблюдать косвенные следы этих частиц (эффекте Казимира) — когда две пластины в вакууме начинают притягиваться из-за этих флуктуаций. Исследования показывают: вакуум — это не фон, а активная среда.

И есть гипотеза, что именно такая микроскопическая флуктуация в далёком "ничто" могла стать тем самым событием, которое запустило Большой взрыв — и с него началась наша Вселенная.

📍 Квантовая теория поля (Quantum Field Theory) —та область физики, которая всё это описывает. Учёные до сих пор пытаются глубже понять природу вакуума, ведь в нём может скрываться ключ к объединению всех фундаментальных сил природы.

1/2

🧠 Что такое Expander-графы и почему это важно?

Помню лет 10-15 назад тема экспандер-графов была очень сильно на слуху. Не знаю как сейчас, вспомнил в связи с нейросетями и их #Interpretability, но даже не знаю, применяются ли там экспандеры...

Однако тема очень прикольная даже независимо от применений...

Expander-граф — это особый тип графа, в котором каждая небольшая группа узлов сильно связана с остальными. То есть даже если случайным образом выбрать 10-20% всех вершин, эти вершины будут иметь множество связей с оставшимися. Граф сохраняет свою «связность» даже при случайном удалении больших частей узлов или рёбер.

📌 Почему это важно? Это имеет большое значение:

— В криптографии: Expander-графы обеспечивают устойчивость к сбоям и атакам.
— В алгоритмах: Они помогают моделировать надёжные и устойчивые системы.
— В теории сложности: Они играют важную роль в решении задач, таких как SAT, и в дискуссиях о проблеме P vs NP.

#ExpanderGraphs #Algorithms #Complexity #SAT #PvsNP

Продолжение 👇

2/2. продолжение. начало тут.

Некоторые подходы к решению задачи SAT используют Expander-графы для создания «жёстких» экземпляров — таких, которые сложно упростить даже при использовании приближённых методов. Это позволяет лучше понять границы между «быстро решаемыми» и «на практике неразрешимыми» задачами.

🔍 Пример: экспандер из 100 узлов, где каждый узел связан с 10 другими. Даже если удалить 20-30% рёбер, граф часто остаётся связанным. Это и есть эффект расширения (expansion).

Кроме того, В таких графах информация распространяется быстро, даже если начинается только с небольшой части узлов. Это свойство делает их так же идеальными для моделирования процессов, таких как заражение, распространение вирусов, распространение новостей и многого другого.

⚙️ Вообще, не зависимо от применений, тут много очень прикольных свойств возникет и это всё не так тривиально, как может показаться на первый взляд, имхо. Надо бы посмотреть более пристально в сторону экспандеров... Думаю, что продолжение на эту тему следует...

#ExpanderGraphs #Algorithms #Complexity #SAT

@easy_about_complex

1/3

Integer Relations - как числа “договариваются” друг с другом?

В мире чисел есть удивительное явление — integer relations. Представьте: у вас есть несколько чисел (например, √2, число π, логарифмы), и вдруг оказывается, что существует способ сложить их с целыми коэффициентами так, чтобы получилось ровно ноль!
Например, π и -π точно дают ноль — это очевидно. Но что, если у вас набор чисел вроде 1, √2 и π — найдётся ли такая “магическая” комбинация? Ответ не всегда очевиден.

Это не просто игра: поиск таких отношений — важнейшая задача в численных вычислениях и теории чисел. Алгоритмы вроде PSLQ могут открыть неизвестные математические связи 👇👇👇

@easy_about_complex

2/3 Продолжение. Начало тут.

🔍 Пример:
есть ли связь между числом π и его квадратом? Рассмотрим вектор чисел:

x = [1, π, π²]

Вопрос: существуют ли такие целые числа a, b, c, не все нули, что:

a·1 + b·π + c·π² = 0 ?

То есть, есть ли целочисленное линейное соотношение между 1, π и π²?

Запускаем алгоритм PSLQ на численно вычисленных значениях этих чисел (до, скажем, 30 знаков). Алгоритм перебирает линейные комбинации с целыми коэффициентами и проверяет, можно ли получить ноль.

👎Результат:
PSLQ не находит никаких нетривиальных целочисленных соотношений. Это подтверждает, что числа 1, π и π² алгебраически независимы (или, по крайней мере, не линейно зависимы над ℚ).
Но теперь попробуем другой пример.


🔍 Пример: формула Мачина для π
Рассмотрим:

x = [π, 4·arctan(1/5), -arctan(1/239)]

Алгоритм PSLQ находит соотношение:

π - 4·arctan(1/5) + arctan(1/239) ≈ 0

Это — формула Мачина (одна из классических формул для вычисления π):

π = 4·arctan(1/5) - arctan(1/239)

👍 Результат: И здесь PSLQ действительно "угадывает" точную алгебраическую формулу по числам с плавающей точкой.


🔥Почему это круто?

Мы из чисел, вычисленных на компьютере, получаем точные формулы.

Это обратный процесс по сравнению с обычной математикой: не от формулы к числу, а от числа к формуле.

Это один из редких примеров, когда компьютер может "угадать" математику.

#ExperimentalMathematics
#IntegerRelations #Algorithms #PSLQ

@easy_about_complex

3/3 Продолжение. Начало тут и тут.

Integer Relations в Квантовой Теории Поля (QFT)

В квантовой теории поля расчёт физических величин (например, аномальных магнитных моментов, поправок к массе и т.д.) требует вычисления многократных интегралов — так называемых Feynman интегралов, часто очень сложных и не имеющих аналитического выражения в явном виде.

Проблема:
Ты вычисляешь интеграл до, скажем, 100 знаков после запятой, но не знаешь, можно ли выразить его через известные константы — π, ζ(3), ln(2), polylogs и т.д.

Решение:
Алгоритмы типа PSLQ позволяют взять численно вычисленное значение и попробовать найти точную комбинацию известных функций, которая даёт тот же результат.

Пример: 3-петлевые поправки в QED
В 1996 году, когда исследовали высшие порядки поправок в квантовой электродинамике (QED), вычислялись 3- и 4-петлевые Feynman диаграммы, численно — и оказалось, что значения можно выразить через комбинации таких чисел, как:

-ζ(3) (дзета-функция Римана)
-π²
-ln(2)
-Li₄(½) (полилогарифмы)

и других “трансцендентных” чисел.

Кейс:
David Broadhurst и David Bailey использовали PSLQ, чтобы найти точные выражения для десятков интегралов, связанных с Feynman diagrams, которые до этого считались "неразрешимыми".

Они буквально открывали формулы из чисел, полученных с суперкомпьютеров — в полном смысле слова "экспериментальная математика в физике".

Почему это важно?
👉Позволяет проверять и упрощать физические расчёты, даже в очень сложных теориях.
👉Помогает предсказать форму результата, прежде чем будет найден аналитический вывод.
👉В некоторых случаях выводит физику на след новых математических объектов — например, множественные дзета-значения (MZV), которые сейчас изучаются и в физике, и в алгебраической геометрии.


📎 Ссылка на эти работы тут.
.
#ExperimentalMathematics
#IntegerRelations #Algorithms #PSLQ #QuantumFieldTheory

@easy_about_complex

🐦Аист, мобила и гопники

В 2017 году польские орнитологи Grupa EkoLogiczna из города Седльце решили отследить миграцию белого аиста. На его спину прикрепили GPS-трекер с SIM-картой.

Аист успешно преодолел около 6000 км и добрался до долины Голубого Нила в Судане. Там местные пацанчики отжали у аиста мобилу с симкой и назвонили в роуменге на 2.5 тысяч евро со счёта польских орнитологов. Конец истории.

#ЧёрныйЮмор #НастроениеЧетверга

🚨 Анонс стрима!

Когда: 11 мая (воскресенье)
🕑 14:00 по Киеву/Москве
🕐 13:00 по немецкому времени

🎥 в этот раз стрим пройдёт на канале Hidden_Heuristic — в воскресенье в указанное время нажмите кнопочку "присоединиться к стриму" сверху! Лучше заходить с компа — слайды будут виднее.

📚 Предварительная программа:
👇👇👇

продолжение. начало тут.

1️⃣ Я расскажу о теории вычислимости и сложности вычислений + сделаю краткий обзор того, что известно о вычислительной мощности рекуррентных нейронных сетей.

2️⃣ Никита — про математику и биологию: введение в нейронауку и обсуждение первых глав книги Peter Dayan Theoretical Neuroscience.

3️⃣ Завершим философией — открытая дискуссия и дебаты. Можете заранее формулировать вопросы!

Очень ждём на стрим также работника в области математики и криптографии -- Диму Топчего (например)

И, конечно же, вас ждут сюрпризы:

Сюрприз от Никиты: он про очень крутую свежую статью в области расскажет! 🔥

Сюрприз от меня: я подофигел вообще от обьёма того что мне прийдётся в воскресенье представить в удобоворимом виде кратко, просто сижу и готовлюсь и не знаю как успеть! до воскресенья вы от меня не увидите больше ни одного сообщения! 😂


#LiveStream