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

🎥 Начинаем выкладывать по маленьким кусочкам записи стрима от 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

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

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

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

#LiveStream #Complexity #Introduction #PvsNP

3/3. Предыдущая часть 👆

Летописи свидетельствуют, что Мерлин недолго ждал следующего поручения.

Одним из нововведений Артура было внедрение вилок. Когда за Круглым Столом накрывали ужин, благородным рыцарям предлагалось оставить мечи и занять отведённые места. Некоторые с удовольствием поедали сочные бараньи ножки, легко доставаемые с помощью прочных вилок. Однако другие быстро нашли более «рыцарское» применение новым приборам и без промедления начали сводить счёты с соседями.

Артуру показалось, что манеры за столом можно было бы значительно улучшить с правильной рассадкой рыцарей. Как и прежде, он вызвал RSA (Royal Secret Agent), который составил граф, показывающий, кто с кем сможет сидеть мирно. Задача найти подходящую рассадку (то, что позже назовут гамильтоновым циклом в графе) снова была поручена Мерлину.

Когда Мерлин понял, что решения нет, он больше не стал прибегать к трюку с 150! диаграммами — он просто написал Кёнигу. Но либо почта шла слишком медленна, либо возникло другое препятствие — ответа Кёнига на это письмо так и не поступило. Не сумев представить решение в установленный срок, Мерлин был приговорён к виселице. Однако приговор был немедленно заменён на «вечность в темнице с возможностью условного освобождения после отбытия одной трети срока».

(c) László Babai
🔗 Источник: László Babai "E-mail and the unexpected power of interaction"

Это была наша новая рубрика #ВГостяхУСказки, а так же подводка к следующему посту про класс сложности IP (интерактивные доказательства - маг Мерлин с безграничными интеллектуальными возможностями и полиномиальный король Артур), а так же про удивительное доказательство теоремы IP=PSPACE.

#Complexity #IP #PSPACE #IPvsPSPACE

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

Почему это важно? Во-первых, этот реультат контр-интуитивный. Считалось, что класс IP это где-то между NP и PSPACE, чуть больше NP, но и близко не дотягивает до PSPACE.

IP - это проверяющий с ограниченным полиномиальным временем мышлением, как король Артур (полином от времени/числа шагов и немного рандома) и неограниченный в вычислительных возможностях доказывающий оракул с сверхспособностями, как Мерлин.

Артур может быть убеждён в любых вещах уровня PSPACE (а это мощный класс задач, например, шахматы), если общается с могучим доказывающим (Мерлин). Это радикально изменило понимание того, насколько мощными могут быть системы доказательств, даже с очень ограниченным проверяющим.

С опорой на классическую PSPACE-полноту задачи верификации кванторной булевой формулы (QBF), Шамир дал то, чего Мерлину так не хватало — мощный, вероятностный протокол убеждения. И у Мерлина появился шанс снова оказаться на свободе.

🖨️ Пока старенький принтер печатал короткий документ, Мерлин завершил вычисления и написал письмо Артуру:

Дата: 26 дек 89, 19:42:14 BST
От: merlin@cave
Кому: arthur

Сир,
в отдельном сообщении я отправляю вам
матрицу M порядка 103 680 300 с элементами
из множества {-1, 0, 1, 2, 3}. Со ссылкой на
L.G. Valiant, TCS 8 (1979), стр. 189–201,
вы без труда убедитесь, что перманент
матрицы M равен 2^{43 200 000}, умноженному
на количество гамильтоновых циклов в
«графе рассадки».

Дайте знать, когда у вас будет время
на полиномиальные вычисления.
С вероятностью 1 - 2^{-1000}
я уверю вас, что этот перманент равен нулю.

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

С уважением,
Мерлин

P.S. Спасибо за подключение к сети.
P.P.S. Что касается компенсации — мне хватит позиции в университете Чикаго.

📍Теперь Мерлин держит путь к Новому Свету. Сначала — Йель (он знал кого-то в тех краях), потом — Великие озёра (Great Lakes).

🍀 Пожелаем ему попутного ветра и продуктивных интеракций.

🔗 Источник: László Babai "E-mail and the unexpected power of interaction"

@easy_about_complex

#ВГостяхУСказки #Complexity #IP #PSPACE #IPvsPSPACE

3/3. предыдущая часть тут 👆

🧠 Подробно и по шагам:

1. Что показывает Уильямс?
Он доказывает, что любую t(n)-временную многоленточную машину можно симулировать с памятью
O(√(t log t)).

То есть: если алгоритм работает за время t(n), то можно смоделировать его в меньшем объёме памяти, чем раньше считалось возможным.

2. Как это используется для разделения P и PSPACE?
Возьмём задачу, решаемую в линейной памяти (s(n) = O(n)) — то есть она точно лежит в PSPACE.

По теореме Уильямса, если бы она решалась за время t(n),
то должно быть:
√(t(n) log t(n)) ≥ n
⇒ t(n) ≥ n² / log n
⇒ t(n) — как минимум квадратичное.

То есть: существуют линейно-памятные задачи, которые не могут быть решены быстрее, чем примерно n².

3. Почему это приближает нас к P ≠ PSPACE?
Класс P включает задачи, решаемые за время O(n^k) для некоторого фиксированного k.

То есть, если бы все задачи из PSPACE решались за полиномиальное время, то было бы P = PSPACE.

Но результат Уильямса показывает, что существуют задачи, которые:
- находятся в PSPACE (решаются в линейной памяти),
- но не решаются быстрее, чем n².

⚠️ Это ещё не доказательство, что они не решаются за любое полиномиальное время (например, n^10),
но это сдвиг границы — от "возможно, они все почти линейные" → "некоторые требуют уже n² или больше".

📌 Вывод:
- Да, n² — это всё ещё полиномиальное время, но важно, что впервые показано, что задачи в линейной памяти не решаются за линейное время. До этого момента в теории сложности удавалось показать лишь слабые верхние и нижние
оценки времени (O(t(n)/log t(n)), Ω(t(n)log t(n)) для задач, решаемых в в линейной памяти, которые всё ещё почти линейные. Но это недостаточно, чтобы показать разделение классов P и PSPACE.
- Это сужает возможное пересечение P и PSPACE.
- Если бы удалось доказать, что задача требует время больше, чем любое полиномиальное, это дало бы P ≠ PSPACE.

@easy_about_complex

#Complexity #P #PSPACE #PvsPSPACE

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

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

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

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

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

#Complexity #PvsPSPACE #P #PSPACE

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

🔐 Гомоморфное шифрование: вычисления без раскрытия данных

Гомоморфное шифрование (Homomorphic Encryption, HE) — это криптографический метод, позволяющий производить вычисления непосредственно над зашифрованными данными. При расшифровке результата вы получите тот же ответ, как если бы вычисляли над исходными данными.

📘 Что это значит на практике?


Пример 1: Защищённая аналитика
-У больницы есть зашифрованные данные о пациентах.
- Исследователь хочет посчитать средний возраст пациентов с диабетом.
- Он выполняет вычисления над зашифрованными данными, не получая доступ к реальным возрастам.
- Результат после расшифровки — корректный, но приватность не нарушена.

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

🔣 Типы гомоморфного шифрования
PHE (частичное): поддерживает одно арифметическое действие (например, схема RSA — умножение, Paillier — сложение).
SHE (ограниченное): ограниченное число операций.
FHE (полное): любые арифметические операции и неограниченное их количество — теоретически мощно, практически сложно.

⚙️ Сложность и ограничения
Полностью гомоморфные схемы (например, BGV, BFV, CKKS) используют сложные математические конструкции, основанные на задачах на решётках (например, Ring-LWE). Они считаются устойчивыми даже к квантовым атакам.
Но:

Один шаг умножения может быть в 1000 раз медленнее, чем над открытыми данными.
Размеры зашифрованных данных могут вырасти в десятки мегабайт даже при обработке маленьких чисел!

Пример 3:
Сравнение времени:
Обычное сложение: ~100 наносекунд
Гомоморфное сложение: ~10–100 микросекунд
Гомоморфное умножение: ~1–10 миллисекунд


Но что, если таких операций — сотни миллионов, как в настоящих аналитических запросах?

🧠 Реальный сценарий, SQL запрос к базе данных:

SELECT AVG(salary) FROM employees WHERE department_id IN (10, 12, 15);

В открытом виде:
-Выполняется за десятки миллисекунд.
- Сложения и фильтрация — почти бесплатные.

В гомоморфной форме (FHE):
- Фильтрация = миллионы сравнений.
- Суммирование и деление — над зашифрованными значениями.- всё дорого.

🔢 Оценка масштабов:
Если один шаг FHE-умножения ≈ 1–10 миллисекунд, а запрос требует 100 млн арифметических операций,
то:

100,000,000×1 мс=1,000,000  секунд≈11.5 дней

🤯 И это — только один запрос.

Да, можно параллелить, батчить, использовать SIMD, но даже с 1000-ядерным распределением это всё ещё часы на простейший аналитический запрос.

🔍 Почему так медленно?
🚫 Невозможно адресовать конкретные данные напрямую: всё обрабатывается последовательно, от начала до конца.
➕ Даже простая фильтрация превращается в арифметическую маску (массив умножений).
🔐 Все операции идут по "защищённому пути": нет читов, нет оптимизаций из классических DB.

🛠️ Что делают?
⚙️ Используют batching (один шифротекст содержит десятки/сотни значений).
⏱️ Переписывают запросы на арифметику, минимизируя глубину схем.
💡 Комбинируют FHE с другими подходами: MPC, TEE, дифференцированным шифрованием.

📌 Вывод:
Гомоморфные вычисления не подходят для произвольных SQL-запросов по большим базам — пока или вообще никогда?

#RealWorldProblems #Crpyptography
#HomomorphicEncryption
#DataPrivacy #Algorithms #Complexity

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

🔢 У 3×3 кубика — около 43 квинтильонов (4 × 10²⁰) возможных конфигураций. И при этом точно известно: любой из них можно решить за максимум 20 ходов. всего за 20, млять, из такого пространства состояний! Это так называемое число Бога. Красивое, минималистичное, почти мистическое.

Меня это сразу зацепило. С одной стороны — гигантское пространство состояний. С другой — маленькое число. Как такое возможно? И как эффективно найти этот кратчайший путь?

📈 Всё это можно представить как блуждание по графу Кэли: каждая вершина — это состояние кубика, рёбра — допустимые повороты. Задача — найти кратчайший путь между двумя вершинами. Логично, что для 3×3 можно просто перебрать всё (хотя и с оптимизациями). Но если взять кубик побольше — n×n×n — задача становится совсем другой.

🤓 Есть мнение, что число Бога растёт квадратично по n. Над этим размышлял даже Теренс Тао — один из самых известных современных математиков. Он предположил, что структура групп конфигураций устроена так, что можно обойтись полиномиальным числом шагов, но... полного доказательства пока нет. Даже у Тао. Это не решённый вопрос.

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

Хотите — расскажу подробности!

🔍 Всё это — не просто про кубик. Это про сложность, алгоритмы, структуру, границы возможного. И, честно говоря, круто, что такая на вид простая штука может вести к таким глубоким вопросам.

Если интересно, могу потом поделиться тем, как всё это связано с криптографией, случайной генерацией и обучением алгоритмов.

А пока — как вы думаете:
а для 4×4 и выше число Бога действительно растёт медленно?
Или просто пока никто не знает?

@easy_about_complex

#Complexity #Algorithms
#ComputationalAlgebra #ComputatinalGroupTheory #CayleyGraphs #Puzzles

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

Теперь начинается самое интересное.

«Алфавит» этой группы — 12 вращений (пo по две вокруг каждой из 6-ти вершин октаэдра — по часовой стрелке и против). Вращения могут переставлять 48 элементов восьми цветов. Всего у пазла 2 009 078 326 886 400 возможных состояний (примерно 2×10^15, около двух квадриллионов).

Если представить все состояния как вершины в графе Кэли, то таких вершин будет столько же — 2 009 078 326 886 400, и из каждой выходит 12 рёбер — по одному на каждое вращение. Найти кратчайший путь от случайно перемешанного состояния к собранному при таком масштабе стандартными алгоритмами практически невозможно, даже на суперкомпьютере.

Поэтому следующий шаг — обучить нейросеть «языку» движений и перестановок именно для этой головоломки. Посмотрим, что получится. Эксперимент продолжается 🙂 Пока не уверен, какую архитектуру выбрать — есть идеи и интуиция, но это надо проверять. Цель на первом этапе — научить нейросеть ориентироваться в огромных пространствах состояний, где при этом есть довольно регулярная структура.

P.S. Напоминаю, что к этому проекту можно присоединиться:
🔗 https://t.iss.one/sberlogabig/581

Ссылки на уже опубликованные работы:
📄 https://arxiv.org/abs/2502.18663
📄 https://arxiv.org/abs/2502.13266

#Algorithms #Complexity #Algebra #GroupTheory #CayleyGraphs #ML #ChristophersJewelPuzzle #Puzzles

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

— Предмет моей лекции, товарищи, — плодотворная вычислительная идея. Что такое, товарищи, P, и что такое, товарищи, NP?
P, товарищи, — это когда решение находят быстро.
NP, товарищи, — это когда быстро лишь проверяют, что нашли правильно.

А что такое, товарищи, идея?
Идея, товарищи, — это вера, что между этими двумя классами всё-таки есть разница… или же её нет.

Кстати, в мае мы делали лайвстрим “Complexity Theory meets Neuroscience”, где какой-то чувак, похожий на меня, давал неформальное введение в теорию сложности.