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 по опыту надо подождать пока все соберутся.

Стрим был очень продуктивным! Кто не пришёл - кусайте локти ) Потому что моя часть стрима не записалась, но Никита дал очень крутую вторую часть и она будет выложена в записи по кусочкам! )

П.С. Да, рано либо поздно, мы научимся записывать стримы

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

кого не добавил в модераторы канала и кто хочет? ) без проблем )

Наш канал порадует уже вас скоро как научным, так и спортивным контентом! Не сдуваемся, держим марку! )