PSPACE-полный
В теории сложности вычислений задача решения является PSPACE-полной, если ее можно решить, используя объем памяти, полиномиальный по входной длине ( полиномиальному пространству ), и если любая другая задача, которая может быть решена в полиномиальном пространстве, может быть преобразована в нее. за полиномиальное время . Задачи, которые являются PSPACE-полными, можно рассматривать как самые сложные проблемы в PSPACE , классе задач решения, решаемых в полиномиальном пространстве, поскольку решение любой такой проблемы можно легко использовать для решения любой другой проблемы в PSPACE.
Задачи, известные как PSPACE-полные, включают определение свойств регулярных выражений и контекстно-зависимых грамматик , определение истинности количественных булевых формул , пошаговые изменения между решениями задач комбинаторной оптимизации, а также множество головоломок и игр.
Теория [ править ]
Задача считается PSPACE-полной, если ее можно решить, используя полиномиальный объем памяти (она принадлежит PSPACE), и каждая задача в PSPACE может быть преобразована за полиномиальное время в эквивалентный экземпляр данной задачи. [1]
Многие подозревают, что PSPACE-полные задачи находятся за пределами более известных классов сложности P (полиномиальное время) и NP (недетерминированное полиномиальное время), но это неизвестно. [2] Известно, что они лежат вне класса NC , класса задач с высокоэффективными параллельными алгоритмами , поскольку задачи в NC могут быть решены в объеме пространства, полиномиальном от логарифма входного размера, и класса задач, решаемых в такой небольшой объем пространства строго содержится в PSPACE по теореме о пространственной иерархии .
Преобразования, которые обычно рассматриваются при определении PSPACE-полноты, представляют собой редукции «многие-единицы» за полиномиальное время , преобразования, которые преобразуют один экземпляр проблемы одного типа в эквивалентный единственный экземпляр проблемы другого типа. Однако полноту также можно определить с помощью сокращений Тьюринга , при которых одна проблема может быть решена за полиномиальное количество вызовов подпрограммы для другой задачи. Неизвестно, приводят ли эти два типа редукций к разным классам PSPACE-полных задач. [3] Также рассматривались другие типы сокращений, такие как сокращения «многие единицы», которые всегда увеличивают длину преобразованного входного сигнала. [4]
Версия гипотезы Бермана-Хартманиса для PSPACE-полных множеств утверждает, что все такие множества выглядят одинаково в том смысле, что все они могут быть преобразованы друг в друга с помощью биекций за полиномиальное время . [5]
Примеры [ править ]
Формальные языки [ править ]
Учитывая регулярное выражение , определение того, генерирует ли он каждую строку в своем алфавите, является PSPACE-полным. [6]
Первой известной PSPACE-полной проблемой была проблема слов для детерминированных контекстно-зависимых грамматик . В словесной задаче для контекстно-зависимых грамматик дается набор грамматических преобразований, которые могут увеличивать, но не могут уменьшать длину предложения, и требуется определить, может ли данное предложение быть произведено с помощью этих преобразований. Техническое условие «детерминизма» (грубо подразумевающее, что каждое преобразование делает очевидным его использование) гарантирует, что этот процесс может быть решен в полиномиальном пространстве, а Курода (1964) показал, что каждая (возможно, недетерминированная) программа, вычислимая в линейном пространстве . пространство можно преобразовать в анализ контекстно-зависимой грамматики таким образом, чтобы сохранить детерминизм. [7] В 1970 году теорема Савича показала, что PSPACE закрыт в условиях недетерминизма, подразумевая, что даже недетерминированные контекстно-зависимые грамматики находятся в PSPACE. [1]
Логика [ править ]
Стандартная проблема PSPACE-полноты, используемая во многих других результатах PSPACE-полноты, представляет собой проблему количественной булевой формулы , обобщение проблемы булевой выполнимости . Задача количественной булевой формулы принимает в качестве входных данных логическое выражение, все его переменные которого количественно определены либо универсально, либо экзистенциально, например:
Реконфигурация [ править ]
Проблемы реконфигурации касаются связности пространства состояний решений комбинаторной задачи. Например, проверка того, могут ли две 4-раскраски графа быть соединены друг с другом ходами, которые меняют цвет одной вершины за раз, сохраняя на каждом этапе допустимую 4-раскраску, является PSPACE-полной. [8] хотя ту же задачу для 3-раскрасок можно решить за полиномиальное время. [9] Другое семейство задач реконфигурации, используемое аналогично количественным булевым формулам в качестве основы для доказательства PSPACE-полноты многих других проблем в этой области, включает в себя недетерминированную логику ограничений , в которой состояния представляют собой ориентации графа ограничений, на которые распространяются определенные ограничения на количество ребра должны быть ориентированы внутрь в каждой вершине, и при этом переходы от состояния к состоянию меняют ориентацию одного ребра на противоположную. [10]
Пазлы и игры [ править ]
Задачу с количественной булевой формулой можно интерпретировать как игру двух игроков: проверяющего и фальсификатора. Игроки делают ходы, которые заполняют значения кванторных переменных в том порядке, в котором они вложены: проверяющий заполняет экзистенциально кванторные переменные, а фальсификатор заполняет универсальные кванторные переменные; игру выигрывает проверяющий, если заполненная формула становится истинной, и фальсифицирующий в противном случае. Количественная формула верна тогда и только тогда, когда проверяющий имеет выигрышную стратегию. Аналогичным образом, проблема определения победителя или проигравшего во многих других комбинаторных играх оказывается PSPACE-полной. Примеры игр, которые являются PSPACE-полными (если они обобщены так, что в них можно играть на доска) — это игры Hex и Reversi . Некоторые другие обобщенные игры, такие как шахматы , шашки (шашки) и го, являются EXPTIME-полными, поскольку игра между двумя идеальными игроками может быть очень продолжительной, поэтому они вряд ли будут находиться в PSPACE. Но они станут PSPACE-полными, если будет соблюдаться полиномиальная граница количества ходов. [11]
Головоломки, в которые играет один игрок, также могут быть PSPACE-полными. Их часто можно интерпретировать как проблемы реконфигурации. [10] и включают в себя пасьянсы «Час пик» , «Маджонг» , «Атомикс» и «Сокобан» , а также механический компьютер «Тьюринг Тамбл» . [11]
PSPACE-полнота основана на сложности как функции размера входных данных. , в пределе как растет без ограничений. Головоломки или игры с ограниченным количеством позиций, например, шахматы на обычной доска не может быть PSPACE-полной, поскольку их можно решить за константное время и пространство, используя очень большую справочную таблицу . Чтобы сформулировать PSPACE-полные версии этих игр, их необходимо модифицировать таким образом, чтобы число позиций в них было неограниченным, например, играя в них на вместо этого доска. В некоторых случаях, например в шахматах, эти расширения являются искусственными.
Ссылки [ править ]
- ^ Перейти обратно: а б с Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), «Раздел 7.4: Полнота полиномиального пространства», Компьютеры и трудноразрешимость: Руководство по теории NP-полноты , WH Freeman, стр. 170–177 , ISBN 0-7167-1045-5
- ^ Арора, Санджив; Барак, Боаз (2009), Вычислительная сложность: современный подход , Cambridge University Press, стр. 92, ISBN 978-1-139-47736-9
- ^ Ватанабэ, Осаму; Тан, Шоу Вэнь (1992), «О полиномиальном времени Тьюринга и многоединственной полноте в PSPACE», Theoretical Computer Science , 97 (2): 199–215, doi : 10.1016/0304-3975(92)90074-P , МР 1163815
- ^ Хичкок, Джон М.; Паван, Адури (2013), «Сокращения, увеличивающие длину для PSPACE-полноты», в Чаттерджи, Кришненду; Сгалл, Ири (ред.), Математические основы информатики 2013 – 38-й Международный симпозиум, MFCS 2013, Клостернойбург, Австрия, 26–30 августа 2013 г., Труды , Конспекты лекций по информатике, том. 8087, Springer, стр. 540–550, номер документа : 10.1007/978-3-642-40313-2_48 , MR 3126236.
- ^ Берман, Л.; Хартманис, Дж. (1977), «Об изоморфизмах и плотности NP и других полных наборов», SIAM Journal on Computing , 6 (2): 305–322, doi : 10.1137/0206023 , hdl : 1813/7101 , MR 0455536
- ^ Хант, Гарри Б. III (1973), «О временной и ленточной сложности языков I», в Ахо, Альфред В.; Бородин, Аллан; Констебль, Роберт Л.; Флойд, Роберт В.; Харрисон, Майкл А.; Карп, Ричард М.; Стронг, Х. Рэймонд (ред.), Труды 5-го ежегодного симпозиума ACM по теории вычислений, 30 апреля - 2 мая 1973 г., Остин, Техас, США , Ассоциация вычислительной техники, стр. 10–19, doi : 10.1145. /800125.804030 , hdl : 1813/6007 , S2CID 15937339 , заархивировано из оригинала 17 января 2024 г.
- ^ Курода, С.-Ю. (1964), «Классы языков и линейно ограниченные автоматы», Информация и вычисления , 7 (2): 207–223, doi : 10.1016/s0019-9958(64)90120-2 , MR 0169724
- ^ Бонсма, Пол; Сереседа, Луис (2009), «Нахождение путей между раскрасками графов: PSPACE-полнота и суперполиномиальные расстояния», Theoretical Computer Science , 410 (50): 5215–5226, doi : 10.1016/j.tcs.2009.08.023 , MR 2573973
- ^ Джонсон, Мэтью; Крач, Дитер; Крач, Стефан; Патель, Виреш; Паулусма, Даниэль (2016), «Нахождение кратчайших путей между раскрасками графа» (PDF) , Algorithmica , 75 (2): 295–321, doi : 10.1007/s00453-015-0009-7 , MR 3506195 , S2CID 6810123
- ^ Перейти обратно: а б Хирн, Роберт А.; Демейн, Эрик Д. (2009), Игры, головоломки и вычисления , А.К. Петерс
- ^ Перейти обратно: а б Эппштейн, Дэвид , Вычислительная сложность игр и головоломок.
Дальнейшее чтение [ править ]
- Сипсер, Майкл (1997), «Раздел 8.3: PSPACE-полнота», Введение в теорию вычислений , PWS Publishing, стр. 283–294 , ISBN 0-534-94728-Х