Друзья!

Если вдруг вы всё ещё не в нашей группе на Facebook — срочно исправляйтесь!

Заходите, не стесняйтесь:
👉 https://www.facebook.com/groups/1199204141422687

Будем рады каждому, даже тем, кто зашёл «просто посмотреть» 😉

Кто из Мюнхена: напоминаю, что уже в эту субботу 24-го мая у нас в городе поэтический вечер/концерт Анны Либерт @frauliebert

Я лично пойду.

#Culture #Poetry #Munich

1/3

🧠 Время и пространство в вычислениях: новая перспектива на разделение классов P и PSPACE


В феврале 2025 года Райан Уильямс из MIT представил работу, которая может стать важным шагом в понимании различий между временной и пространственной сложностью алгоритмов.

🧩 Почему P ⊆ PSPACE — это просто, а обратное — сложно?
Интуитивно понятно, что если алгоритм работает за полиномиальное время (класс P), то он не может использовать больше памяти, чем времени, ведь за каждый шаг он может использовать не более одного нового блока памяти. Поэтому P ⊆ PSPACE.

Однако доказать, что PSPACE ⊆ P, крайне трудно. Это связано с тем, что память можно переиспользовать: мы можем записывать данные, удалять их и использовать ту же область памяти снова. Время же — это однонаправленный ресурс: его нельзя "перезаписать" или "переиспользовать". Это делает время более ограниченным ресурсом по сравнению с пространством/памятью.

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

2/3. начало тут 👆

🧠 Что нового в работе Уильямса?
Уильямс показал, что любую многоленточную машину Тьюринга, работающую за время t(n), можно симулировать, используя всего O(√(t log t)) памяти. Это значительное улучшение по сравнению с предыдущим результатом 1975 года, где требовалось O(t / log t) памяти. Ключевым элементом этого достижения стало использование эффективного алгоритма для задачи оценки деревьев, недавно разработанного Куком и Мерцем (2024).

🔍 Почему это важно для P vs PSPACE?
Результат Уильямса - любую задачу, решаемую за время t(n), можно просимулировать, используя всего O(√(t log t)) памяти. Это означает, что временные вычисления можно очень эффективно "перевести" в пространственные, и при этом не требуется много памяти.

Теперь главный момент:

Если можно симулировать любые временные вычисления с такой малой памятью, то можно сделать обратное предположение:
задачи, которые требуют даже линейной памяти, не могут быть решены за полиномиальное время. А это уже прямой шаг к разделению классов PSPACE и P.

Конкретнее:

✳️ Формальное следствие из результата Уильямса (Corollary 1.2) - существуют задачи, которые можно решить с памятью
n, но никакой алгоритм не сможет их решить за время меньше, чем почти n². Это ещё не доказывает, что они вне P,
но приближает нас к такому доказательству.

Результат Уильямса не показывает, что задача из PSPACE не в P (т.е. не опровергает P = PSPACE напрямую),
а показывает, что существуют задачи, решаемые в линейной памяти, которые не могут быть решены за время n^k для любого фиксированного k — то есть не в P, если бы это удалось доказать для всех полиномов.

Но сейчас доказано только, что они не решаются быстрее, чем n².
Это ещё не доказывает, что они вне P, но приближает нас к такому доказательству.

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

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

#НастроениеПятницы - в Мюнхене на днях

#Munich

В рамках рубрики #НастроениеПятницы девушка, которая подписана на наш канал и моя очень давний и хороший друг прислала такую картинку 👇👇👇

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

Был сегодня на поэтическом вечере Анны — 1,5 часа пролетели как 15 минут. Очень классный перформанс, Анна здорово держит сцену и вовлекает. Атмосфера уютная, публика приятная — прямо хорошее время! В завершении была песня, где Анна поёт совместно с ИИ, да-да — необычно и по-своему трогательно.

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

Анна сейчас ездит с выступлениями по городам Германии, а скоро будет в Екатеринбурге (привет нашим подписчикам из России). Если снова заглянет в Мюнхен — пойду ещё раз без раздумий.

Рекомендую, особенно если вам важна не только поэзия, но и то, как она подаётся.

#Culture #Poetry #Munich

@frauliebert
https://www.instagram.com/frauliebert/

P.S. Пару видео сейчас добавлю в комментарии

#НастроениеВоскресенья #АйтишныйЮмор

Напоминаю про лекцию Хинтона в пятницу, онлайн👇👇👇

А наш стрим в телеге уже в это воскресенье, 1.06, днем или вечером! Будет много AI, AGI и их математических основ. Окончательный анонс следует.

#LiveStream

🔬 Нобелевский лауреат Джефри Хинтон (тот самый крёстный отец ИИ) видимо, посмотрел наш прошлый лайв-стрим и решил не отставать — читает лекцию на ту же тему, что мы разбирали на прошлом стриме: "Биологические и цифровые нейросети".

🎓 Лекцию можно будет посмотреть онлайн 30.05: 👉 https://www.rigb.org/whats-on/discourse-digital-intelligence-vs-biological-intelligence

Не благодарите 😄

#AI #Hinton #Brain #DeepLearning #LiveStream

🎙 В это воскресенье, 1 июня, состоится наш очередной стрим!
⠀
В последние недели особо не было времени на подготовку, поэтому математики будет совсем немного (но она всё же будет!).
⠀
Зато мы позволим себе немного уйти в философию и попытаемся закрыть некоторые психологические гештальты: что такое мышление и сознание в самом общем виде — без эзотерики, но с интересом и размышлениями.
⠀

#LiveStream

Кстати, все больше и больше запросов поступает чтобы стримы были действительно международными - кто готов переходить на английский? )

Мне легче немецкий, но я и по-английски смогу, а вы? ;)

🧠 Напоминаю: сегодня стрим!

🕔 17:00 (Центральноевропейское время)
🕕 18:00 (Киев / Москва)

На этот раз — меньше математики, больше философии.
Поговорим об искусственном и естественном интеллекте:
что они могут, чем отличаются и куда всё это идёт.

Подключайтесь! 💬✨

стрим начался. я отойду на пару минут, всё равно минут 5-10 по опыту надо подождать пока все соберутся.