Истории (не)успеха (ИИ)ЕИ

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