Классы сложности вычислений: За пределами P и NP
Когда речь заходит о теории сложности, большинство ограничивается обсуждением проблемы P против NP. Однако вселенная вычислительных задач гораздо шире и многообразнее. В дискретной математике и теории алгоритмов существует сложная иерархия классов, которая помогает понять пределы возможностей не только современных процессоров, но и будущих квантовых компьютеров. Что происходит, когда задача требует не просто бесконечного времени, но и бесконечной памяти?
Класс NP охватывает задачи, решение которых можно быстро (за полиномиальное время) проверить. Но существуют задачи, для которых даже проверка ответа является невероятно трудной. Здесь мы переходим в класс PSPACE.
PSPACE (Polynomial Space) — это класс задач, которые можно решить, используя полиномиальный объем памяти (ОЗУ), при этом время вычислений алгоритма вообще не ограничивается (оно может быть экспоненциальным). В этот класс попадает большинство сложных стратегических настольных игр. Например, чтобы определить, существует ли у белых выигрышная стратегия в обобщенных шахматах (на доске размером N×N) или в игре Го, компьютеру не нужно хранить в памяти все возможные партии. Достаточно перебирать ходы в глубину, экономя память, но этот перебор займет миллиарды лет. Доказано, что NP является подмножеством PSPACE: любая NP-задача решается в PSPACE, но обратное неизвестно.
Еще выше в иерархии стоит класс EXPTIME (Exponential Time). Это задачи, которые гарантированно требуют экспоненциального времени для решения, вне зависимости от того, какой алгоритм мы придумаем. Если для проблемы P=NP ученые еще надеются найти быстрый алгоритм, то для EXPTIME-полных задач математически доказано, что быстрого решения в природе не существует (согласно теореме об иерархии времени).
Связь между памятью и временем в информатике описывается знаменитой Теоремой Сэвича (Savitch's Theorem), доказанной в 1970 году. Теорема гласит, что если какую-то задачу можно решить на недетерминированном компьютере с использованием памяти S(n), то ее можно решить и на обычном детерминированном компьютере, используя память не более чем S(n)^2 (квадрат от исходного объема). Это одно из самых красивых доказательств в теории сложности, показывающее, что недетерминизм (магия угадывания) дает экспоненциальный прирост по времени, но лишь квадратичный прирост по памяти.
