🧠 Пару недель назад мы писали про свежий удивительный результат, касающийся времени и пространства/памяти в вычислениях:

👉 https://t.iss.one/easy_about_complex/1027

🎥 Теперь вышло наглядное и увлекательное видео на YouTube, которое объясняет этот результат простыми словами (на английском):

📺 How to squeeze space into time — видео от ChalkTalk

Рекомендуем к просмотру всем, кто интересуется теорией вычислений и просто красивыми идеями! 🚀

#Complexity #PvsPSPACE #P #PSPACE

🧠 Мы не просто так говорим про математику, физику и информатику - мы создаём машину времени 😁😎😇

Вот тут и тут — мы обсуждали потрясающие, неожиданные научные результаты 2025 года. Современная наука бьёт током: прорывы, новые методы, неожиданные связи.

Но вот вопрос: а какие открытия в прошлом были сопоставимы по масштабу?
Что так же резко сдвигало представление о возможном?

💡 Давайте посмотрим?
Сделаем серию постов, где пройдёмся по историческим открытиям — от более близкого к более далёкому прошлому. Посмотрим, чем жила фундаментальная наука — и как эти открытия повлияли на наш мир.

📆 Начнём, пожалуй, со второй половины XX века — и будем спускаться вниз: по десятилетиям, а потом и векам.

🗞️ Первая остановка — ноябрь 1979 года.
В газете The New York Times выходит статья с заголовком:
“A Soviet Discovery Rocks World of Mathematics”
(«Советское открытие потрясает мир математики»).

Звучит громко.
А вот в чём там прикол — расскажу вам (после)завтра.

Оставайтесь на связи 📡

@easy_about_complex

Начало тут 👆

📚 В этом канале и на стримах (тут и тут) мы уже не раз обсуждали фундаментальные вопросы вычислительной сложности:

Что такое классы P и NP:
- Почему вопрос "P = NP?" — один из величайших нерешённых в математике?
- И что вообще значит «решить задачу за полиномиальное время»?

Теперь давайте посмотрим на задачу, которая стала поворотной точкой между прикладной оптимизацией и теоретической информатикой.
Речь о линейном программировании (или линейной оптимизации) — и прорыве, который произошёл в 1979 году.

🔧 Что такое линейная оптимизация?
Это класс задач, где нужно оптимизировать линейную функцию при наличии линейных ограничений.
То есть: что-то максимизировать или минимизировать, соблюдая заданные условия.

💡 Пример:
Составить рацион питания из доступных продуктов — так, чтобы:
-покрыть все суточные нормы по питательным веществам (ограничения),
- но потратить как можно меньше денег (целевая функция).

С 1947 года такие задачи эффективно решались с помощью симплекс-метода — разработанного Джорджем Данцигом.

📈 На практике метод довольно хорош: миллионы логистических, экономических и инженерных систем полагались (и полагаются) на симплекс.

Но была проблема:
⚠️ в теории симплекс может работать экспоненциально долго. А значит, мы не знали, принадлежит ли линейная оптимизация к классу P (полиномиально вычислимых задач).

💥 1979: появляется Хачиян

И вот, в 1979 году Леонид Хачиян, молодой математик из СССР, предлагает эллипсоидный метод — первый алгоритм, который решает задачу линейного программирования за гарантированное полиномиальное время.

🌀 Идея метода:

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

📉 Но на практике метод оказался медленным (см. сноску внизу 🍒). А вот в теории он дал главное:

🔐 Он доказал, что линейная оптимизация ∈ P.
То есть: существует "быстрый алгоритм" (см. сноску внизу 🍒).

🧩 А теперь — мост к комплексити-теории
Вот почему это открытие было настолько важно:

До Хачияна не было известно, попадает ли линейная оптимизация в класс P.

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

Она показала, что не всякая полезная задача сложна. Некоторые — фундаментально решаемы эффективно (см. сноску внизу 🍒).

А ещё — это вдохновило целую волну исследований:
📈 появились внутренние точечные методы (например, метод Кармаркара), которые были не только полиномиальными, но и быстрыми на практике.

📌 Итог
Линейное программирование — редкий случай задачи, которая:
- 🔧 реальная прикладная задача,
- ✅ и точно в классе P.

Да, в реальной жизни симплекс чаще всего быстрее,
но именно эллипсоид Хачияна навсегда изменил теоретическое понимание линейной оптимизации.

🧠 А теперь — маленькая

загадка:
Как так получается,
что теоретически «быстрый» эллипсоид на практике
почти всегда проигрывает по времени
теоретически «медленному» симплексу?

📌 Подумайте:
метод эллипсоида и полиномиальное время — это гарантия на худший случай, а не обещание быть быстрым всегда.

А симплекс?
Возможно, во многих случаях он просто умеет "угадывать", где находится решение — даже если не обещает ничего формально для всех случаев (см. сноску внизу 🍒).

👉 И в этом — вся красота прикладной математики.
И вся хитрость теории сложности.

@easy_about_complex

#P #NP #PvsNP #LinearProgramming
_

🍒 сноска: есть нюансы! По сути эллипсоидный метод требует полиномиального времени с очень высокой степенью полиномов. Это значит, что эллипсоидный метод Хачияна начнёт бить симплекс-метод по времени вычислений на практике только начиная с какого-то определённого размера оптимизационной задачи и выше? (worst case ✅ average case❓). Вот с каких порядков задачи симплекс-метод начнёт уступать методу эллипсоидов - я сейчас не могу сказать. Надо разбираться в деталях. Я слышал(?), что в в последние годы в больших вычислительных центрах, где реально большие задачи эллипсоид таки бьёт симплекс (worst case?average case?practical cases?). Но это не точно.

🧠 В последнее время мы много говорили о математике, теории сложности, об искусственном и естественном интеллекте и прочих фундаментальных вещах. А вот про повседневную практику софт-разработки — почти не вспоминали.

Хочу это исправить. В ближайших постах планирую рассказать о трёх проектах из более чем дюжины, которыми я занимался за последние 15 лет для крупных и известных компаний. Это не теория, не хобби и не pet-проекты — это рабочие системы, созданные за деньги и реально используемые в серьёзных продуктах.

Начнём с трёх проектов, довольно разных, но каждый — на стыке инженерии и высоких технологий:

🔬 Медицина — софт в приборах для микрохирургии глаза.
Это safety-critical система: пациент не должен ослепнуть из-за бага в коде или перегоревшего транзистора в железе.

🏗️ Машиностроение — системы управления продвинутой индустриальной 3D-печатью.
Пожалуй, самый высокотехнологичный продукт, над которым я когда-либо работал.

🔐 Криптография — гомоморфное шифрование в реальных системах, с реальными пользователями.
Работает ли это на практике или остаётся в теории?

На днях расскажу, как эти проекты были устроены, с какими техническими (и не только) вызовами мы сталкивались и чему я сам из них научился.

📡 Оставайтесь на связи — будет интересно даже тем, кто далёк от программирования.

продолжение следует на днях

#RealWorldProblems #SoftwareEngineering #SoftwareQuality

1/2

Как обещал вверху 👆, расскажу о паре реальных проектов в интересных областях, над которыми мне довелось работать в последние годы.

💡 Работал над Callisto Eye — системой для микрохирургии глаза. Прежде всего удаление катаракты и имплантация искусственных линз.

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

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

⚙️ В проекте я отвечал за контроль качества и интенсивно использовал автоматизацию тестов на реальном hardware(см. картинку👆).

Продолжение — про технические и алгоритмические вызовы 👇

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

⚙️ В проекте Callisto Eye я отвечал за контроль качества. Один из главных вызовов — реалистичные автоматические тесты на реальном железе, которые симулируют целый рабочий день хирурга. Они должны были ловить даже мельчайшие сбои: функциональные ошибки, утечки памяти, взаимные блокировки (deadlocks), нарушения в синхронизации потоков, неожиданные задержки в UI — всё, что может проявиться только в долгосрочном, живом сценарии.

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

Среди множества задач особенно запомнились две.
Одна — чисто техническая.
Вторая — методологическая и по-настоящему новая.

🧩 Проблема 1: установка софта через CI (Continuous Integration) на кастомном "железе"
Callisto Eye — это не просто приложение, которое можно поставить из пакетного менеджера. Это полноценная ОС + tightly coupled системные компоненты, заточенные под определённый стек железа. Поэтому мы тестировали целые образы жёсткого диска, чтобы полностью воспроизвести окружение, как в операционной. CI должен был уметь автоматически прошивать систему этим образом, с нуля и надёжно — каждый раз. Сетевая загрузка (PXE boot) немного усложняла жизнь и с ней пришлось повозиться, но это хотя бы известная штука.. А вот вторая проблема стала по-настоящему новым вызовом.

🔍 Проблема 2: как быть уверенным, что сами автотесты не врут?
Автотест — это тоже софт. А если в нём баг? Что, если тест "зелёный", а на деле хирург в разгар операции увидит пустой экран?
Цена ошибки — зрение пациента. Поэтому пришлось разработать целую методологию и алгоритмический фреймворк, чтобы верифицировать надёжность самих тестов.
К сожалению, пока не оформил это в полноценную статью — руки не дошли. Хотя я неоднократно выступал на различных конференциях по медицинской технике с этой темой и рассказывал про это устно:
👉 https://medtechstars.eu/schedule/dmitrychibisov/

Из опубликованного — есть только старая статья (там ещё не всё понимание было сформировано, но всё же кое-что есть, если вдруг кому интересно):
📄 https://www.researchgate.net/publication/370595971_Patterns_of_Test_Automation

@easy_about_complex

#RealWorldProblems #SoftwareQuality #TestAutomation #SoftwareDevelopment #MedTech #Engineering

P.S. Следующий пост про real-world-проекты будет из области современного машиностроения и продвинутой индустриальной 3d-печати. Но сначала немного теории и вообще науки 👇👇👇

🎓 Чередуем практику и теорию. Свежее интервью Теренса Тао "Hardest Problems in Mathematics, Physics & the Future of AI"

С теоретическими темами у нас, кажется, удивительно хорошее чутьё на тренды. Пару недель назад после нашего стрима про искусственные vs. биологические нейросети — лекцию на ту же тему прочитал сам нобелевский лауреат Джеффри Хинтон.

Недавно мы рассуждали о вычислимости природы вообще (и тут) с моделированием законов природы машиной Тьюринга (это не такая распостранённая тема в научных кругах на сегодняшний день), краем затронули странности в газовой и гидродинамике, возникающие на разных уровнях описания — от микроскопического к макроскопическому, P?=NP и т.д.. И вот буквально вчера выходит интервью Терренса Тао (Филдсовская медаль, один из крупнейших математиков современности) — где он затрагивает в точности эти же вопросы.

Они у нас списывают, как думаете? 😂 Шучу, скорее всего они вообще о нашем существовании не подозревают. Но факт остаётся: в теоретических темах мы до сих пор как-то стабильно попадаем в точку и раньше всех затрагиваем самые острые темы.

Про некоторые моменты в интервью Теренса Тао я напишу на днях, но рекомендую посмотреть, самое то перед сном (интервью на английском):

👉https://www.youtube.com/watch?v=HUkBz-cdB-k

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

👉 https://t.iss.one/easy_about_complex/1073

Активнее, друзья! Пишите ваши мнения и приглашайте своих друзей!

Небольшое превью-головоломка к следующему посту про практику и реальные индустриальные задачи 😎


До этого проекта я был уверен, что все индустриальные задачи это только механика+электроника+софт. Во время работы над этим проектом осознал, что к этой троице можно добавить еще и химию/материаловедение )


Это была наша новая рубрика. Не знаю даже как её назвать. Первый вариант названия #ДасИстФантастиш. Второй вариант названия - #Оху@ть

Кто за первый вариант ставьте - ❤️
Кто за второй вариант ставьте - 😇

1/2

🧠💥 Математика, которая может взорваться — загадка уравнений Навье–Стокса

Это одна из тем, про которые говорил Теренс Тао в своём интервью в субботу.

Представьте: вы плеснули водой — она закружилась, вспенилась, но в конце концов всё улеглось. А теперь вообразите, что это не всегда так. Что в какой-то момент движение воды начинает концентрироваться, сжиматься и разгоняться настолько, что скорость её частиц становится бесконечной. Это — сингулярность, "взрыв", и до сих пор неизвестно, может ли он реально возникнуть.

💸 Именно этот вопрос — будет ли решение уравнений Навье–Стокса оставаться гладким в любой момент времени, или же, при определённых начальных и граничных условиях, случится разрыв? — и лежит в основе одной из Задач тысячелетия. За её решение — миллион долларов. А суть в следующем: уравнения Навье–Стокса описывают поведение жидкостей и газов, но они настолько сложны и нелинейны, что могут вести себя непредсказуемо.

🧑‍🏫Тао подошёл к этой проблеме нестандартно...

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

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

Но сначала вернёмся от Теренса Тао на почти 100 лет назад к работам Андрея Колмогоровa.

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

Андрей Колмогоров в 1941 году предложил статистическую теорию турбулентности, которая не пытается предсказать каждое завихрение, а описывает их в среднем. Он задался вопросом: Как распределяется энергия в турбулентном потоке между завихрениями разных размеров, по шакале от метров до мили-, микро-,- и т.д. метров?

Как распределяется энергия в турбулентном потоке между завихрениями разных размеров?

📐 Формула Колмогорова: 𝐸(𝑘) ∼ 𝑘⁻⁵⸍³
Здесь:
— 𝐸(𝑘) — энергетический спектр: сколько энергии содержится в завихрениях размера, соответствующего волновому числу k;
— 𝑘 — волновое число, обратно пропорциональное размеру вихря: чем больше k, тем мельче вихрь
— ∼ 𝑘⁻⁵⸍³ — энергия убывает с ростом k по степенному закону: чем мельче завихрение, тем меньше в нём энергии.
📉 Крупные вихри содержат больше энергии, и по мере распада потока на всё более мелкие — энергия «перетекает вниз». Это и есть энергетический каскад Колмогорова.

📌 Почему это важно?
Формула 𝐸(𝑘) ∼ 𝑘⁻⁵⸍³ — это золотой стандарт в турбулентности. Её подтверждали во множестве экспериментов: от потоков в трубах до атмосферных ветров.

📡 В спектре турбулентности вы реально видите "горку", убывающую как 𝑘⁻⁵⸍³, между зоной внешних сил (где поток "раскачивается") и зоной вязкости (где энергия гасится).

🤝 Колмогоров и Тао
Колмогоров предложил макроскопическую модель: что делает турбулентность в среднем. А Тао, десятилетия спустя, пытается понять:

А возможно ли, чтобы вся энергия сконцентрировалась в одной точке — чтобы вместо каскада вниз случился взрыв вверх, сингулярность?

🔍 Что сделал Тао:

1. Создал модифицированную модель Навье–Стокса
Тао предложил упрощённые версии уравнений — не настоящие Навье–Стокса, а их "игровые" аналоги. Он отключил некоторые физические ограничения, но сохранил важные структурные черты, чтобы изучить, возможен ли в принципе сценарий сингулярности.

2. Показал, что в этих уравнениях возможен blow-up
Он построил пример, где энергия жидкости стекается в одну точку всё быстрее и быстрее, пока не становится бесконечной за конечное время. Это — математическая модель сингулярности.

🧠 Главная идея:

Если слегка ослабленные уравнения могут "взорваться", значит, в оригинальных уравнениях такие механизмы где-то на грани — и, возможно, их можно "выдавить" или, наоборот, доказать, что они невозможны.

📈 Его идея: представить сценарий, где вихри в жидкости ведут себя как программа, которая самовоспроизводится — каждый раз в меньшем масштабе и с большей скоростью. Такая каскадная структура ведёт к тому, что вся энергия стягивается в одну точку, ускоряясь бесконечно — как жидкостная версия компьютера, с встроенным механизмом “взрыва”.

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

В своём интервью он наглядно объясняет, как с помощью конструкции типа машины Тьюринга он перепрограммирует уравнения Навье-Стокса не на рассеивание энергии через механизмы транспорта и вязкости на отдельные вихри, а пускает энергию вниз по масштабам через вихри большего размера к вихрям меньшего и ещё меньшего и т.д. размера. Очень интересный метод. Мне понра и захотелось даже заглянуть в его оригинальную статью 2016-го года. Надо отметить что подобные темы мы уже разбирали тут и тут.

#NavierStockes #MilleniumPrize #Kolomogorov #Tao #MathPhysics

@easy_about_complex

1/2

Реальные проекты: индустриальная 3D-печать

Не скажу, что этот проект — мой любимый, но пару лет я провёл в индустрии 3D-печати, работая в компании EOS. В технические дебри самой печати вдаваться не буду — тут я не эксперт. В общих чертах: специальные материалы + мощные лазеры → предметы слой за слоем вырастают из полимеров или металлических сплавов. Kак в этом посте, где я уже это показывал результат 3д-печати.

Сама технология сложная, но моя зона ответственности была вполне конкретной: я контрибьютил в код на C++ и занимался автоматическим тестированием (моя любимая часть работы 🛠️).

Архитектура у системы интересная: вся машина делится на две софт-компоненты — UI под Windows (тачскрин, понятный интерфейс для человека) и real-time-компонент, работающий либо на микроконтроллерах, либо, как у нас, на PLC. которая управляла моторами, лазерами и получала данные от датчиков.

Продолжение следует 👇

Начало тут👆

И вот тут был один важный урок: в нашем случае под Windows находилась не только визуальная оболочка, но и логика машины. Это оказалось архитектурной ошибкой — логику пришлось переносить в real-time-систему. Мой опыт: логика должна жить в real-time-части, под Виндоуз — только UI.

Бонусом разобрался с OPC UA-это такой HTTP для промышленных машин: умные устройства общаются по сети друг с другом напрямую. Автоматизация + коммуникация = индустрия будущего.

Опыт был полезный, особенно в плане архитектурных решений и тонкостей real-time-систем. Хороший пример того, как не стоит проектировать… и как потом правильно переделывать🙂

Потом эта история мне пригодилась.Где-то год назад на собеседовании спросил у руководителя разработки:

"А где у вас логика живёт — под Виндоуз или на микроконтроллерах?"
Он: "На микроконтроллерах."
Я: "Фух. А то пришлось бы всё переделывать."
И всё — через пару дней прилетает оффер на тим-лида в техномашиностроительную компанию 😄 Опыт — сын ошибок трудных, как говорится.

1/2
🧊 Сверхпроводимость, симметрия и немного здоровой иронии

Автор: М. Кацнельсон. (Фейсбук)

Теория сверхпроводимости BCS (БКШ, Бардин-Купер-Шриффер, истинные патриоты добавляют еще Боголюбова, и нельзя сказать, что совсем безосновательно), почитаемая одним из высших достижений теоретической физики всех времен и народов, была создана в 1957 году.

Они написали некую модель (основанную на предыдущей работе Купера) и нашли приближенное решение вариационным методом (который, как потом показал Боголюбов, является асимптотически точным в термодинамическом пределе).

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

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

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

И только в 1984 году мы показали [📎Ссылка на статью], что в исходной задаче, в модели БКШ, эта концепция просто не нужна, ответ может быть получен при строгом сохранении числа частиц, при этом, что важно, выкладки не сложнее, чем у БКШ, даже технического выигрыша от нарушенной симметрии в этой конкретной задаче нет.

Как повезло человечеству, что мы сделали эту работу в 1984 году, а не в 1956. Правда, в 1956 году нам было бы ее сделать затруднительно, чисто в силу принципа причинности.

(c) Mikhail Katsneltson. 20.06.2014.


П.С. Может быть Михаил Кацнельсон заглянет на один из следующих лайв-стримов в этом канале, но это ещё не точно. Поэтому, друзья, поставьте лайки и сердечки, чтобы Михаил точно пришёл

@easy_about_complex

#Superconductivity #BCS #Katsneltson

Помните, мы писали про забавную историю из мира AI-стартапов? Вот еще в копилку 👇👇👇