P-полный
-
Определение P-полноты
- P-полная задача — это задача, которая может быть решена за полилогарифмическое время на P-машине.
- P-полнота является свойством, которое позволяет доказать, что задача не может быть решена быстрее, чем за полилогарифмическое время.
-
Примеры P-полных задач
- Задача о логической выполнимости — проверка выполнимости формулы логики высказываний.
- Задача о стоимости схемы — вычисление стоимости схемы, учитывая ее топологию.
- Линейное программирование — максимизация линейной функции при линейных ограничениях.
- Лексикографический поиск — определение порядка посещения вершин в графе.
- Принадлежность к контекстно-свободной грамматике — проверка возможности генерации строки грамматикой.
- Хорн-выполнимость — проверка существования решения для набора предложений Хорна.
- Игра жизни — определение состояния ячейки после заданного числа шагов.
- LZW сжатие — проверка добавления строки к словарю с помощью алгоритма LZ78.
- Вывод типа для частичных типов — определение наличия частичного типа у нетипизированного термина.
-
Доказательства P-полноты
- Для доказательства P-полноты задачи часто пытаются свести известную P-полную задачу к рассматриваемой.
- Цзинь-И Цай и Д. Сивакумар показали, что если существует разреженный язык, который является P-полным, то L = P.
-
Примеры задач, не являющихся P-полными
- Некоторые NP-задачи не являются ни NP-полными, ни P-полными, но считаются сложными.
- Существуют задачи в P, которые не являются ни P-полными, ни NC, но считаются сложными для распараллеливания.
Полный текст статьи: