В теории сложности вычислений задача решения является P-полной ( полной для класса сложности P ), если она находится в P и каждая проблема из P может быть сведена к ней путем соответствующего сокращения.
Понятие P-полных задач решения полезно при анализе:
особенно когда рассматриваются более сильные понятия сводимости, чем поливременная сводимость.
Конкретный тип используемого сокращения варьируется и может влиять на конкретный набор проблем. Обычно используются сокращения, более сильные, чем сокращения за полиномиальное время, поскольку все языки в P (кроме пустого языка и языка всех строк) являются P -полными при сокращениях за полиномиальное время. Если мы используем NC- редукции, то есть сокращения, которые могут работать за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров, то все P -полные задачи лежат вне NC и поэтому не могут быть эффективно распараллелены при недоказанном предположении, что NC ≠ П . Если мы используем более сильную редукцию лог-пространства , это остается верным, но дополнительно мы узнаем, что все 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-complete . Эта проблема иллюстрирует распространенный прием в теории 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 также могут быть решены за линейное время.
Некоторые NP -задачи не известны как NP - полные или в P. Эти проблемы (например , факторизация , изоморфизм графов , игры на четность ) считаются трудными . Точно так же в P существуют проблемы , о которых неизвестно, являются ли они P -полными или NC , но считается, что их трудно распараллелить. Примеры включают в себя формы задачи решения: найти наибольший общий делитель двух чисел, определить, какой ответ вернет расширенный алгоритм Евклида, если даны два числа, и вычислить максимальное соответствие весов графа с большими целочисленными весами.
