Введение
В теории вычислительной сложности, задача принятия решения является P-полной (полной для класса сложности P), если она принадлежит классу P и любая задача из P может быть сведена к ней подходящим приведением. Понятие P-полных задач полезно при анализе:
какие задачи трудно эффективно распараллеливать,
какие задачи трудно решать при ограниченном объеме памяти, особенно когда рассматриваются более строгие понятия приводимости, чем полиномиальная приводимость. Конкретный тип приведения может варьироваться и влиять на точный набор задач. Обычно используются приведения, более сильные, чем приведения за полиномиальное время, поскольку все языки в P (за исключением пустого языка и языка всех строк) являются P-полными при полиномиальных приведениях. Если мы используем NC-приведения, то есть приведения, которые могут выполняться за полилогарифмическое время на параллельном компьютере с полиномиальным числом процессоров, то все P-полные задачи лежат вне класса NC и, следовательно, не могут быть эффективно распараллелены, при недоказанном предположении, что NC ≠ P. Если мы используем более сильное логарифмическое приведение по памяти, это остаётся верным, но дополнительно мы узнаём, что все P-полные задачи лежат вне класса L при более слабом недоказанном предположении, что L ≠ P. В этом последнем случае множество P-полных задач может быть меньше.
which problems are difficult to solve in limited space. specifically when stronger notions of reducibility than polytime reducibility are considered. The specific type of reduction used varies and may affect the exact set of problems. Generically, reductions stronger than polynomial time reductions are used, since all languages in P (except the empty language and the language of all strings) are P complete under polynomial time reductions. If we use NC reductions, that is, reductions which can operate in polylogarithmic time on a parallel computer with a polynomial number of processors, then all P complete problems lie outside NC and so cannot be effectively parallelized, under the unproven assumption that NC ≠ P. If we use the stronger log space reduction, this remains true, but additionally we learn that all P complete problems lie outside L under the weaker unproven assumption that L ≠ P. In this latter case the set P complete may be smaller.
Мотивация
Класс 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-полными
Некоторые NP-задачи неизвестно, являются ли они NP-полными или принадлежат классу P. Считается, что эти задачи (например, факторизация, изоморфизм графов, игры на четность) сложны. Аналогично, существуют задачи в классе P, которые неизвестно, являются ли они P-полными или NC, но предполагается, что их трудно распараллелить. Примеры включают в себя варианты задач принятия решений, связанные с нахождением наибольшего общего делителя двух чисел, определением результата работы расширенного алгоритма Евклида для двух заданных чисел и вычислением максимального взвешенного паросочетания в графе с большими целочисленными весами.