P-полный

В теории сложности вычислений задача решения является P-полной ( полной для класса сложности P ), если она находится в P и каждая проблема из P может быть сведена к ней путем соответствующего сокращения.

Понятие P-полных задач решения полезно при анализе:

• какие проблемы сложно эффективно распараллелить,
• какие задачи сложно решить в ограниченном пространстве.

особенно когда рассматриваются более сильные понятия сводимости, чем поливременная сводимость.

Конкретный тип используемого сокращения варьируется и может влиять на конкретный набор проблем. Обычно используются сокращения, более сильные, чем сокращения за полиномиальное время, поскольку все языки в P (кроме пустого языка и языка всех строк) являются P -полными при сокращениях за полиномиальное время. Если мы используем NC- редукции, то есть сокращения, которые могут работать за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров, то все P -полные задачи лежат вне NC и поэтому не могут быть эффективно распараллелены при недоказанном предположении, что NC ≠ П. ​Если мы используем более сильную редукцию лог-пространства , это остается верным, но дополнительно мы узнаем, что все P -полные проблемы лежат вне L при более слабом недоказанном предположении, что L ≠ P . В этом последнем случае множество P -полных может быть меньше.

Мотивация

Класс P , который обычно включает в себя все «решаемые» проблемы для последовательного компьютера, содержит класс NC , который состоит из тех проблем, которые могут быть эффективно решены на параллельном компьютере. Это связано с тем, что параллельные компьютеры можно моделировать на последовательной машине. Неизвестно, является NC = P. ли Другими словами, неизвестно, существуют ли какие-либо решаемые проблемы, которые по своей сути являются последовательными. Точно так же, как широко распространено подозрение, что P не равно NP , так же широко распространено подозрение, что не равно P. NC

Аналогично, класс L содержит все задачи, которые может решить последовательный компьютер в логарифмическом пространстве. Такие машины работают за полиномиальное время, поскольку могут иметь полиномиальное количество конфигураций. Предполагается, что L ≠ P ; то есть некоторые проблемы, которые можно решить за полиномиальное время, также требуют большего, чем логарифмическое пространство.

Подобно использованию NP-полных задач для анализа вопроса P = NP , P -полные проблемы, рассматриваемые как «вероятно нераспараллеливаемые» или «вероятно по своей сути последовательные» проблемы, аналогичным образом служат для изучения вопроса NC = P. вопрос. Поиск эффективного способа распараллеливания решения некоторой P -полной задачи показал бы, что NC = P . Это также можно рассматривать как «задачи, требующие суперлогарифмического пространства»; решение P -полной проблемы в лог-пространстве (с использованием определения, основанного на сокращении лог-пространства) будет подразумевать L = P .

Логика, лежащая в основе этого, аналогична логике, согласно которой решение NP -полной проблемы за полиномиальное время доказывает P = NP : если у нас есть NC- редукция от любой проблемы из P к проблеме A и NC- решение для A, тогда NC = P. ​Аналогично, если у нас есть лог-пространственная редукция любой проблемы из P к проблеме A и лог-пространственное решение для A, то L = P .

P-полные проблемы

Самая основная P -полная проблема при редукции «много-один» в пространстве журналов следующая: дана машина Тьюринга $M$, входные данные для этой машины x и число T (записанное в унарном формате ), $\langle M,x,T\rangle$ эта машина останавливается на этом вводе в течение первых T шагов? Для любого x в $L$ в P выведите кодировку машины Тьюринга, которая принимает ее за полиномиальное время, кодировку самого x и количество шагов $T=p(|x|)$ соответствующий p, который ограничен полиномиальным временем работы машины Тьюринга. $M_{L}$ решение $L$, $\langle M,x,p(|x|)\rangle$. Машина M останавливается в точке x в течение $p(|x|)$ шаги тогда и только тогда, когда x находится в L. Очевидно, что если мы сможем распараллелить общую симуляцию последовательного компьютера (т. е. симуляцию машины Тьюринга машиной Тьюринга), то мы сможем распараллелить любую программу, которая работает на этом компьютере. . Если эта проблема существует в NC относится и к любой другой проблеме в P. , то то же самое Если количество шагов записано в двоичном формате, проблема EXPTIME-complete .Эта проблема иллюстрирует распространенный прием в теории P -полноты. Нас не особо интересует, можно ли быстро решить задачу на параллельной машине. Нас просто интересует, решит ли параллельная машина гораздо быстрее, чем последовательная. нам придется переформулировать задачу так, чтобы последовательная версия находилась в P. Поэтому Вот почему эта проблема требовала, чтобы T было записано в унарном виде. Если число T записано как двоичное число (строка из n единиц и нулей, где n = log T ), то очевидный последовательный алгоритм может занять время 2 ^н . С другой стороны, если T записано как унарное число (строка из n единиц, где n = T ), то это займет всего лишь время n . Записав T в унарном, а не двоичном формате, мы сократили очевидный последовательный алгоритм с экспоненциального времени до линейного. Это ставит последовательную задачу в P . Тогда он будет в NC тогда и только тогда, когда его можно распараллелить.

Было доказано, что многие другие задачи являются P -полными и поэтому широко считаются по своей сути последовательными. К ним относятся следующие проблемы, которые являются P -полными, по крайней мере, при сокращении лог-пространства, либо как задано, либо в форме задачи решения:

• Задача значения схемы (CVP). Учитывая схему , входы схемы и один вентиль в схеме, вычислите выход этого вентиля.
• Ограниченный случай CVP. Как и CVP, за исключением того, что каждый вентиль имеет два входа и два выхода (F и Not F), каждый второй уровень представляет собой просто вентили И, остальные — вентили ИЛИ (или, что то же самое, все вентили являются вентилями И-НЕ или все вентили). вентили являются вентилями ИЛИ), входы вентиля поступают из непосредственно предыдущего слоя
• Линейное программирование . Максимизируйте линейную функцию с учетом ограничений линейного неравенства.
• Лексикографически первый порядок поиска в глубину. Учитывая граф с фиксированными упорядоченными списками смежности и узлами u и v , посещается ли вершина u перед вершиной v при поиске в глубину, вызванном порядком списков смежности?
• Членство в контекстно-свободной грамматике. Учитывая контекстно-свободную грамматику и строку, может ли эта строка быть сгенерирована этой грамматикой?
• Выполнимость по Хорну – существует ли набор предложений Хорна , присвоив переменную, которая им удовлетворяет? Это предложенная P. версия проблемы булевой выполнимости ,
• Игра «Жизнь». Учитывая начальную конфигурацию «Игры жизни» Конвея , конкретную ячейку и время T (в унарном формате), жива ли эта клетка после T шагов?
• LZW (алгоритм) (парадигма 1978 года) Сжатие данных – учитывая строки s и t , добавит ли сжатие s с помощью метода LZ78 t в словарь? (Обратите внимание, что для сжатия LZ77 , такого как gzip , это намного проще, поскольку проблема сводится к «Is t in s ?».)
• Вывод типа для частичных типов. Учитывая нетипизированный термин из лямбда-исчисления , определите, имеет ли этот термин частичный тип.

Большинство вышеперечисленных языков являются P -полными при еще более строгих понятиях редукции, таких как равномерный $AC^{0}$ сокращения «многие единицы», сокращения DLOGTIME или полилогарифмические проекции.

Чтобы доказать, что данная проблема в P является P -полной, обычно пытаются свести известную P -полную задачу к заданной.

В 1999 году Джин-И Цай и Д. Сивакумар, опираясь на работу Огихары, показали, что если существует разреженный язык, который является P -полным, то L = P .

P -полные задачи могут быть решены с разной временной сложностью . Например, проблема стоимости схемы может быть решена за линейное время с помощью топологической сортировки . Конечно, поскольку редукция к P -полной задаче может иметь различную временную сложность, этот факт не означает, что все задачи из P также могут быть решены за линейное время.

Ссылки

• Гринлоу, Рэймонд, Джеймс Гувер и Уолтер Руццо. 1995. Пределы параллельных вычислений; Теория P-полноты . ISBN   0-19-508591-4 . — Разрабатывает теорию, затем каталогизирует 96 задач P-Complete.
• Сатору Мияно, Сюдзи Сираиси и Такаеси Сёдай. Список P-полных задач , Университет Кюсю, RIFIS-TR-CS-17 , декабрь 1990 г.