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

напоминаю, сегодня стрим в канале https://t.iss.one/hidden_heuristic.

начало в 13:00 по немецкому времени, в 14:00 по Киеву/Москве

Какая-то техническая заминка с началом стрима. Момент

🎥 Стрим длиной 3.5 часа подошёл к концу — было очень интересно и насыщенно!

Кто не пришёл — кусайте локти. Но аккуратно: запись будет. Хотя кусайте всё равно, потому что часть стрима не записалась 😅

📚 Были две основные презентации:
— от меня: краткое введение в теорию вычисломости/сложности вычислений + разбор одного результата про вычилительную мощность рекуррентных нейронных сетей 🧮
— от Никиты: введение в теоретическую нейронауку -- матаппарат нейробиологов 🧠

🧠 Кроме того, Дима сделал мини-презентацию со своим видением решения задачи тысячелетия: P ≠ (?) NP.

🔥 Было много вопросов, комментариев и обсуждений — спасибо всем, кто участвовал!

💬 Также получилась живая дискуссия о практическом значении задачи P ≠ (?) NP — спасибо Диме и Владимиру за мысли!

📅 Планируем продолжать такие стримы и дальше — углубляться в пересечения математики, IT и нейронаук. Stay tuned!🧮

#LiveStream

Друзья, накидывайте темы и направления на следующие стримы. Вот один вариант предложенный Никитой 👇👇👇

Видео этого стрима будет в нарезках по темам через какое-то количество дней. Но уже думаем над следующими стримами. Кому интересно что-то рассказать, представить, узнать, обсудить - пишите!

Вводная статья об AIXI - определение "универсального интеллекта" в theorethical computer science:
https://arxiv.org/abs/0712.3329v1

Для чего это нужно?
Условно закрыть философский гештальт: «а что такое интеллект в самом общем смысле?»

Сегодня на стриме Дмитрий, в частности, показал, что RNN могут в теории эмулировать произвольную машину Тьюринга. Я вижу, конечно, с этим проблему в том, что на практике вы никогда не получите веса связей из множества Кантора с желаемой точностью. Результат интересный, но для практического описания реальных возможностей ИИ не подходит.

Популярно об AIXI еще можно почитать в книге Сбербанка, смотрите комментарий к посту)

🎥 Начинаем выкладывать по маленьким кусочкам записи стрима от 11 мая — "Complexity Theory meets Neuroscience".

Если пропустили в прямом эфире или хотите пересмотреть отдельные моменты — самое время!

Самое начало стрима 👆👆👆

Stay tuned 🧠⚡

#LiveStream #PureMath #AppliedMath #Complexity #Neurscience

🎥 Хайлайты лайв-стрима от 11 мая — "Complexity Theory meets Neuroscience".

Дима очень кратко и чётко рассказывает о своём видении решения задачи тысячелетия: P ≠ (?) NP. Владимир вносит несколько важных уточнений касаемо практической значимости строгого математического доказательства этой фундаментальной проблемы. Завязывается дискуссия и дебаты, но в итоге ребята приходят к консенсусу! Так же затронута тема квантовых вычислений и мостик между квантовыми алгоритмами и классической теорией сложности алгоритмов.👆👆👆

Продолжение следует! Stay tuned 🧠⚡

#LiveStream #Complexity #PvsNP #QuantumComputing

Кто не все понял в этом видео 👆 - не расстраивайтесь. Скоро будут нарезки из стрима с введением в эти темы.

AIXI - гипотетический идеал Искусственного Общего Интеллекта (Artificial General Intelligence - AGI).

❓Кто умнее — вы или AGI?

Представьте, что вы проходите тест на IQ и вам нужно продолжить числовой ряд: 2, 4, 6, 8, …

Первый инстинкт — ответить «10». Но что, если я скажу, что этот ряд также удовлетворяет сложному полиному:
2k⁴ − 20k³ + 70k² − 98k + 48, согласно которому следующее число в последовательности 58, а не 10!

Как же понять, какое продолжение правильное?

Вот тут на помощь приходит принцип бритвы Оккама из философии — выбор самого простого и краткого объяснения (или алгоритма), которое описывает данные.

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

AIXI использует именно такой подход: он ищет самый короткий алгоритм, который объясняет наблюдаемые данные, и на его основе делает прогнозы — он выбирает наиболее вероятную, простую и универсальную модель мира.

продолжение тут 👇👇👇

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

Как работает AIXI?

AIXI просматривает все возможные вычислимые модели мира и взвешивает их по вероятности, отдавая предпочтение тем, что имеют меньшую колмогоровскую сложность — проще говоря, выбирает "самую лаконичную правду".

Почему AIXI не существует на практике?

Главная проблема — невычислимость. Соломоновская индукция, лежащая в основе AIXI, теоретически оптимальна, но невозможно вычислить её точно на реальном компьютере. Это связано с тем, что поиск по всем возможным программам бесконечен и слишком затратен по ресурсам — ни один компьютер не сможет просмотреть и оценить все варианты.

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

В результате, AIXI — это идеал, математическая модель, к которой стремятся многие алгоритмы ИИ, но которую невозможно реализовать полностью.

Зачем тогда изучать AIXI?

Потому что он задаёт эталон, к которому можно стремиться. Современные алгоритмы машинного обучения и ИИ — это приближения к AIXI. Чем больше у них ресурсов, тем лучше они могут выбирать модели и делать прогнозы.

Понимание AIXI помогает понять фундаментальные ограничения и возможности искусственного интеллекта и понять, что значит интеллект в принципе.

🧠 И вот где прикол:
Число 10 — это логичное продолжение самой простой гипотезы: шаг +2.

Но! Также можно построить много других гипотез, например:

Полином 𝑎(𝑘)=2𝑘⁴ − 20𝑘³ + 70𝑘² − 98𝑘 + 48. Он тоже даёт значения: 2, 4, 6, 8 при 𝑘=1,2,3,4, но на 𝑘=5 даёт 58.

AIXI не "предпочитает" 58, он говорит: все гипотезы возможны, но каждая имеет свою вероятность.

❓Так кто умнее?
Человек, отвечая "10", опирается на контекст и социальное ожидание от задачи.

AGI, построенный по принципу AIXI, не имеет контекста, он математически оценивает вероятности всех гипотез — и выдаёт взвешенное предсказание на основе всех возможных алгоритмов, в том числе и "неинтуитивных".

@easy_about_complex

#AGI #AIXI #Solomonoff

Продолжем выкладывать нарезки стрима „Complexity Theory meets Neuroscience“ от 11.05.2025.

Начало краткого неформального введения в теорию сложности, для тех, кто не совсем понял о чём тут говорят Дмитрий и Владимир.

Продолжение следует! Stay tuned 🧠⚡

#LiveStream #Complexity #Introduction #PvsNP

1/3
При дворе короля Артура жили 150 рыцарей и 150 дам.

«Почему бы не создать 150 супружеских пар?» — размышлял король, и мысль немедленно была претворена в действие. Он поручил Королевскому Секретному Агенту (Royal Secret Agent = RSA) составить диаграмму, включающую все 300 имён, указывая красной линией взаимный интерес между дамой и рыцарем, а при его отсутствии — синей линией. Диаграмма с 150² = 22 500 цветными линиями выглядела довольно запутанно, но не настолько, чтобы запутать Мерлина, придворного мага, которому Артур передал её с чётким приказом: найти совершенное соответствие между дамами и рыцарями (по взаимной любви).

Мерлин удалился, посмотрел на диаграмму и,благодаря своему безграничному интеллекту, мгновенно понял, что ни одна из 150!(≈5×10^262) возможных пар не даёт полностью красного соответствия. Он быстро перебрал все 5×10^262 диаграмм, выделив в каждой ошибочную линию, и приказал слугам отнести их в тронный зал как доказательство того, что Артур потребовал невозможного.
Продолжение👇