В теории вычислительной сложности задача принятия решений является P-полной ( полной для класса сложности P ), если она принадлежит P и каждая задача из P может быть сведена к ней с помощью соответствующей редукции.
Понятие P-полных задач принятия решений полезно при анализе:
особенно когда рассматриваются более сильные понятия сводимости, чем поливременная сводимость.
Конкретный тип используемой редукции варьируется и может влиять на точный набор задач. В общем случае используются редукции, более сильные, чем редукции полиномиального времени, поскольку все языки в P (кроме пустого языка и языка всех строк) являются P -полными при редукции полиномиального времени. Если мы используем NC- редукции, то есть редукции, которые могут работать за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров, то все P -полные задачи лежат вне NC и, следовательно, не могут быть эффективно распараллелены при недоказанном предположении, что NC ≠ P. Если мы используем более сильную редукцию логарифмического пространства , это остается верным, но дополнительно мы узнаем, что все P -полные задачи лежат вне L при более слабом недоказанном предположении, что L ≠ P. В этом последнем случае множество P -полных задач может быть меньше.
Класс P , который обычно считается состоящим из всех «решаемых» проблем для последовательного компьютера, содержит класс NC , который состоит из тех проблем, которые могут быть эффективно решены на параллельном компьютере. Это связано с тем, что параллельные компьютеры могут быть смоделированы на последовательной машине. Неизвестно, является ли NC = P . Другими словами, неизвестно, существуют ли какие-либо решимые проблемы, которые по своей сути являются последовательными. Так же, как широко распространено подозрение, что P не равно NP , широко распространено подозрение, что NC не равно P .
Аналогично, класс 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 -полная проблема при логарифмически-однозначных сокращениях следующая: дана машина Тьюринга , вход для этой машины x и число T (записанное в унарной системе ), останавливается ли эта машина на этом входе в течение первых T шагов? Для любого x в P выведите кодировку машины Тьюринга, которая принимает его за полиномиальное время, кодировку самого x и количество шагов, соответствующих p, которое является полиномиальной границей для операции машины Тьюринга, решающей , . Машина M останавливается на x в течение шагов тогда и только тогда, когда x находится в L. Очевидно, что если мы можем распараллелить общую симуляцию последовательного компьютера (т. е. симуляцию машины Тьюринга машиной Тьюринга), то мы сможем распараллелить любую программу, которая работает на этом компьютере. Если эта задача в NC , то и любая другая задача в P . Если количество шагов записано в двоичной системе, задача является EXPTIME-полной . Эта задача иллюстрирует распространенный трюк в теории P -полноты. На самом деле нас не интересует, можно ли быстро решить задачу на параллельной машине. Нас интересует только, решает ли ее параллельная машина намного быстрее последовательной. Поэтому нам нужно переформулировать задачу так, чтобы последовательная версия была в P . Вот почему эта задача требовала, чтобы T была записана в унарной системе счисления. Если число T записано как двоичное число (строка из n единиц и нулей, где n = log T ), то очевидный последовательный алгоритм может занять время 2 n . С другой стороны, если T записано как унарное число (строка из n единиц, где n = T ), то он займет всего лишь время n . Записав T в унарной системе счисления, а не в двоичной, мы сократили очевидное последовательное время с экспоненциального до линейного. Это помещает последовательную задачу в P . Тогда она будет в NC тогда и только тогда, когда она параллелизуема.
Было доказано, что многие другие проблемы являются P -полными, и поэтому широко распространено мнение, что они по своей сути последовательны. К ним относятся следующие проблемы, которые являются P -полными по крайней мере при сокращениях логарифмического пространства, либо как заданные, либо в форме задачи принятия решения:
Большинство из перечисленных выше языков являются P -полными при даже более сильных понятиях редукции, таких как равномерные многоединичные редукции, редукции DLOGTIME или полилогарифмические проекции.
Чтобы доказать, что данная задача в P является P -полной, обычно пытаются свести известную P -полную задачу к данной.
В 1999 году Джин-И Цай и Д. Сивакумар, основываясь на работе Огихары, показали, что если существует разреженный язык , который является P -полным, то L = P. [1 ]
P -полные задачи могут быть решены с различной временной сложностью . Например, задача о значении схемы может быть решена за линейное время с помощью топологической сортировки . Конечно, поскольку сведения к P -полной задаче могут иметь различную временную сложность, этот факт не означает, что все задачи в P также могут быть решены за линейное время.
