🎄 «Цыплят по осени считают», как гласит народная мудрость. А какая научная работа в этом году заставила вас сказать «ВАУ»?

Да, до Нового года ещё аж целых три месяца, коллеги , но почему бы уже не начать подводить итоги? Что сделали физмат-науки за этот год, что вас действительно впечатлило?

В моём поле зрения оказалось два ярких кандидата на результат года:

1️⃣ Теория сложности: свежий взгляд на разделение классов P и PSPACE — новое понимание времени и пространства в вычислениях.
2️⃣ Матфизика: шаг к решению 6-й проблемы Гильберта — корректный предельный переход между неравновесной термодинамикой и уравнениями Навье–Стокса.

Но интересно не только моё мнение:
💡 Какие работы этого года заставили вас сказать «вау»? В любой области науки.
Давайте вместе составим наш рейтинг 2025 года! 🏆

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

Планируется вернуться к систематическому разбору интересных результатов и идей из физики и математики: от классических тем до современных направлений.

Начнём, пожалуй, с двух областей, которые на первый взгляд кажутся далёкими друг от друга, — теории сложности и теории категорий.
Какая между ними связь? На самом деле — самая прямая: категории всё чаще используются для формализации вычислений, а сложность можно рассматривать через структуру морфизмов и преобразований.

Поговорим о том, как абстрактные конструкции помогают лучше понимать вычисления, алгоритмы и границы того, что вообще можно эффективно посчитать.

Оставайтесь на связи — впереди будет много математики!

Читаю сейчас работу моего друга Димы Топчий про равенство классов P и NP. Разбираюсь, вникаю. Признаюсь - пока много не понимаю. Но во всяком случае меня не покидает ощущение, что мы стоим на пороге чего-то великого. Или по крайней мере сногсшибательного. Пока мне лично много не понятно, но Дима всегда готов на лайв-стрим, где может ответить на вопросы.

С моей стороны, я предлагаю, немного покопаться в этой работе прежде чем задавать вопросы автору

Работа находится в ревью в знаменитом журнале Theoretical Computer Science, ну а мы с вами имеем возможность прочитать уже сейчас и задать вопросы автору, который, кста, модератор в этом канале и сам может писать посты :-)

И есть пояснительная бригада в виде меня и остальных ребят, которые либо из computer science, либо из математики.

Друг мой Дима, ребята, вот последняя версия. Дима, пожалуйста, удали версию pdf выше.

По результатам опроса готовлю краткое видео-введение в теорию сложности и проблему тысячелетия P vs. NP . Если есть какие-то пожелания к видео-введению (где углубиться, например, а что проскочить) - пишите в комментариях. Mожет быть вы хотите какие-то определённые вещи из этой обширной темы - не стесняйтесь, пишите.

Лайв-стрим с Димой Топчий про его подход к P vs. NP тоже готовится. Оставайтесь на связи!

Вообще у нас было уже введение в теорию сложности в рамках лайв-стрима «Complexity Theory meets Neueoscience“. Но я сейчас хочу его перезаписать и был бы бесконечно благодарен вам, дорогие друзья, за отзыв - что в этом видео не понятно, или наоборот тривиально и можно проскочить, а где желательно углубиться. Любые критические комментарии и пожелания приветствуются! Заранее спасибо!

👇👇👇

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

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

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

#LiveStream #Complexity #Introduction #PvsNP

Кстати, Владимир, который был на стриме, - моё почтение! Это уже классный специалист в theoretical computer science! ВШЭ (его Alma mater).

На днях умер Чак Норрис, который выключал свет быстрее чем свет гас.

«Большинство людей сдаются за секунду до того, как сделать что-то, к чему они так стремились и что показалось им невыполнимым. Делать это, конечно же, нельзя. Ведь ты никогда не можешь сказать заранее, какое препятствие на твоем пути окажется последним»

— Чак Норрис

Пока я готовлю видео-лекцию по введению в теорию сложности, и готовлюсь к лайв-стриму с Димой Топчим по его фундаментальной работе в этой области, решил немного развлечь вас, дорогие друзья.

На этих выходных я вышел из зоны комфорта — причём вышел далеко — и выступил на опен-майке со стендапом на украинском языке.

Хоть я родом из Украины, но много лет живу в Германии и на украинском не говорил. Так что это был редкий случай, когда человек учит язык прямо на сцене, рассказывает шутки/наблюдения, ставит неправильно ударения в каждом втором слове, запинается на каждом третьем слове. Забывает, чем закончил предыдущее предложение в начале каждого следующего, постоянно смотрит в бумажку. В общем - полный позор. Однако зал все равно встретил тепло, видимо за старание.

Может быть нужно чаще выходить из зоны комфорта и пробовать новый опыт, новые языки?

позориться так позорится - но каждый раз более профессионально? Напишите ваше мнение в комментариях!

https://www.youtube.com/watch?v=6DV6d1pqwPE

Дима Топчий работает с какой-то космической скоростью — пока я только готовлю видео-лекцию с введением в теорию сложности, он уже успел записать объяснение собственного решения решения одной из её центральных задач:

https://www.youtube.com/watch?v=2X7s8wdJxjY

Если не всё понятно из этого видео, то не переживайте 🙂 Дождитесь моего вводного видео: я постараюсь объяснить всё так, чтобы смысл задачи стал ясен и инженерам, и гуманитариям.

А после этого устроим онлайн-стрим — обсудим всё вместе с Димой, разберём детали и и Дима ответит на наши вопросы.

У кого уже сейчас есть вопросы по Диминому докaзательству равенства классов P и NP - не стесняйтесь, задавайте вопросы в комментариях.

🏛 Информационная сложность на пальцах: почему больше — не значит лучше

От двоичного счета до падения империй — ищем универсальную «Золотую середину» Вселенной.

Помните прикол: сколько чисел можно показать на пальцах двух рук? 🤔

Обычный человек скажет: «Десять!» Но любой информатик поправит: «Вообще-то, 1024».

Как это работает? Представьте, что каждый палец — это выключатель. У него всего два состояния: либо он поднят (1), либо опущен (0).

Один палец — это 2 варианта.

Два пальца — уже 4 варианта (00, 01, 10, 11).

Три пальца — 8 вариантов...
С каждым новым пальцем количество комбинаций удваивается. В итоге для десяти пальцев мы получаем 2^10 = 1024 комбинации. Мы носим в карманах мощный инструмент для счета, просто не всегда об этом догадываемся!

Но почему бы не пойти дальше? Если добавить пальцам третье состояние — например, «полусогнутый» — мы сможем кодировать уже 3^10, а это 59 049! Казалось бы, вот она — бесконечная мощь! Но тут мы упираемся в стену.

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

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

Мы не можем добавлять всё больше и больше состояний наших пальцев, чтобы кодировать больше чисел - система потеряет надёжность и эффективность.

📉 Конфликт мощности и надёжности

В теории информации есть понятие эффективности кодирования. Это всегда компромисс между между информационной плотностью и надёжностью:

1️⃣ Информационная плотность: Мы хотим, чтобы каждый «символ» (палец) нес как можно больше данных.

2️⃣ Стоимость распознавания (шумоустойчивость): Получатель должен безошибочно отличать одно состояние от другого.

Попробуйте быстро показать другу число «три-четверти-согнутого-мизинца». Скорее всего, он вас не поймет. В системе с 2 состояниями разница между «да» и «нет» огромна. Ошибиться невозможно. В системе с 10 состояниями различие между ними становится мизерным.

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

📐 Золотая середина: f(k) = k^(1/k)

Математики нашли точку, где эти весы приходят в идеальное равновесие. Используется функция, сравнивающая выигрыш от количества состояний (k) с ценой их поддержания (1/k):

f(k) = k^(1/k)

Если построить график этой функции, мы увидим, что сначала она резко растет, но после определенного момента сложность начинает «съедать» пользу. Пик этой кривой — математический идеал — приходится на число Эйлера: e ≈ 2,718

В физическом мире мы выбираем между целыми числами. Математически 3 ближе к идеалу, чем 2. Именно поэтому троичная логика считается самой эффективной, а БОЛЬШЕ 3 — НЕ ЗНАЧИТ ЛУЧШЕ.

⚛️ Универсальная математика компромиссов

Этот принцип управляет не только битами в современных компьютерах, но и много чем ещё:

В ядерной физике: Добавление частиц в ядро увеличивает энергию связи. Но с ростом массы начинает мешать электростатическое отталкивание. Итог — «железный пик» (ядра около железа самые стабильные). Все, что сложнее или проще, стремится к этому балансу.

В биологии: Крупные организмы эффективнее мелких в расходе энергии. Но бесконечно расти нельзя — кости не выдержат вес, а сердце не прокачает кровь. Природа всегда ищет точку, где размер дает преимущество, но не убивает систему.

В истории и бизнесе: Масштаб дает ресурсы, но порождает «комбинаторный взрыв» внутренних связей. Когда система растёт, её ресурсы увеличиваются линейно (больше территорий = больше налогов), а сложность внутренних связей растёт экспоненциально.
В маленькой группе информация передается мгновенно, но в гигантской империи она тонет в бюрократии.Когда количество чиновников и регламентов растёт быстрее, чем доходы от новых территорий, система переходит «точку e». Она начинает тратить всю свою энергию на обслуживание самой себя, теряет гибкость и в итоге рушится под собственным весом. Империи и корпорации-гиганты часто гибнут не от внешних ударов, а от неспособности справиться с собственной сложностью (конкретные примеры - Римская Империя, СССР и Nokia в своё время). .

✅ Итог: Математика пределов

Мир не стремится к бесконечности. Он стремится к точке идеального баланса.

Оптимальное решение почти никогда не лежит на краю шкалы. Оно всегда где-то посередине. Математика — это не просто цифры, это напоминание о границах возможного и искусстве вовремя остановиться.

В следующем сообщении мы продолжим эту тему и рассмотрим как пример крах плановой экономики в СССР попутно перейдя к алгоритмической сложности и проблеме тысячелетия #PvsNP.

@easy_about_complex

#Complexity #EulersNumber #InformationTheory

🏛 Алгоритм распада: СССР сквозь призму теории сложности

В предыдущем посте мы выяснили, что на пальцах двух рук можно досчитать до 1024, а не только до десяти, и что число e ≈ 2,718 — это не просто константа из учебника, а жесткий предел эффективности любой системы.

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

История СССР — это, пожалуй, самый масштабный в истории человечества «краш-тест» системы, которая попыталась проигнорировать законы вычислительной сложности.

Почему Советский Союз не смог пережить информационную эпоху? Мы привыкли винить падение цен на нефть, гонку вооружений или «предательство элит».

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

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

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

1. Проклятие размерности и P vs NP 🧩

Если 1920-е годы экономика была «линейной» и достаточно было контролировать десяток базовых отраслей (уголь, сталь, зерно), чтобы страна работала, то к 1970-м годам в СССР производилось n = 25 000 000 наименований изделий. Математически это не просто список, а граф, где узлы — это товары, а ребра — связи между ними: чтобы выпустить один подшипник, нужен металл, смазка, энергия, станки. Каждый из n товаров зависит от множества других. Количество прямых и косвенных связей в такой сети растет как n². Для советской экономики это 625 триллионов связей.

Связи нелинейны: изменение цены на электроэнергию в Иркутске по длинной цепочке графа меняет себестоимость хлеба в Ташкенте и добычи никеля в Норильске. Изменение в одном узле (например, засуха на юге или авария на шахте в Норильске) по цепочке рикошетит по всей системе, требуя пересчета миллионов других параметров.

Но настоящая катастрофа — в вычислительной сложности. Здесь мы упираемся в главную проблему информатики: P vs NP.

Есть два класса сложности вычислительных задач:

🔹Класс P: Задачи, которые компьютер решает быстро. Если у нас есть готовый план, мы можем за «разумное» время посчитать, сколько ресурсов на него уйдет. Это полиномиальная сложность.

🔹Класс NP: Задачи, где мы можем быстро проверить правильность решения, если нам его дадут, но найти его с нуля невероятно сложно.

Глобальная оптимизация экономики (поиск самого лучшего плана из всех возможных) — это NP-трудная задача. Математически это означает, что не существует (или пока не найдено) алгоритма, который нашел бы идеальное распределение ресурсов быстрее, чем за экспоненциальное время, т.е. существенно быстрее чем за время 2ⁿ.

При n = 25 000 000 Госплану потребовалось бы время, превышающее возраст мироздания . Это и есть комбинаторный взрыв: система «зависает», пытаясь произвести вычисления такого объёма ⏳.

В чём секрет успеха рыночной экономики по сравнению с плановой?
Госплан пытался централизованно решить одну гигантскую NP-трудную задачу, стремясь к глобальному оптимуму, что в принципе требует перебора пространства порядка 2ⁿ вариантов. Рыночная же экономикa работает иначе и представляет из себя децентрализованный эвристический алгоритм, который не ищет недостижимый «абсолютный идеал», а находит достаточно хорошие решения через миллиарды локальных взаимодействий ⚙️ В результате глобальная NP-трудная задача фактически распадается на множество распределённых подзадач, которые решаются параллельно «на лету» 🚀 Там, где плановая система пыталась всё просчитать заранее, рынок просто адаптивно вычисляет состояние экономики в реальном времени.

Я, конечно, несколько упрощаю, в политбюро тоже не совсем дураки сидели. Hа самом деле ситуация несколько сложнее.
Но давайте разбираться дальше, и с экономикой, и с математикой...

2. Ловушка выбора: Почему нельзя «дать всем всё»? ⚖️

Часто спрашивают: «Почему бы просто не дать каждому заводу столько ресурсов, сколько ему нужно?». Математика и экономика отвечают: потому что ресурс — это всегда выбор.

🛑 Дефицит альтернатив: Если вы отдадите всю сталь на тракторы, вам не из чего будет строить корабли. Ресурсы (энергия, материалы, рабочее время) всегда ограничены. Дать одному — значит забрать у другого. Это игра с нулевой суммой в рамках ресурсов планеты.

🛑 Информационная энтропия: Без рыночного сигнала (цены) у потребителя нет стимула экономить. Каждый директор завода будет требовать ресурсов «с запасом» на случай сбоев. В итоге потребности системы мгновенно раздуваются до бесконечности, создавая фиктивный дефицит.

🛑 Альтернативная стоимость (Opportunity Cost): Нужно ежесекундно решать, где тонна алюминия принесет больше пользы — в кастрюлях или в крыльях самолета? Чтобы ответить на это для 25 миллионов товаров, нужно учесть весь граф связей одновременно.

Именно здесь возникает критическая точка невозврата, где математическая сложность экономики окончательно переросла возможности управляющего субъекта (Госплана).

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