Класс P
Содержание
Определение
Определение: |
Класс [1]. | — класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:
Итого, язык лежит в классе тогда и только тогда, когда существует такая детерминированная машина Тьюринга , что:
- завершает свою работу за полиномиальное время на любых входных данных;
- если на вход машине подать слово , то она допустит его;
- если на вход машине подать слово , то она не допустит его.
Свойства класса P
Лемма: |
Класс сведения по Карпу. . замкнут относительно |
Доказательство: |
Пусть — разрешитель , работающий за полиномиальное время. . Построим разрешитель для языка .Разрешитель if ( ) return true return false работает за полиномиальное время, так как композиция полиномов есть полином. |
Лемма: |
. В частности, из этого следует, что . |
Доказательство: |
Понятно, что . Докажем, что .. Пусть Представим себе разрешитель — разрешитель , работающий за полиномиальное время и использующий оракул языка . Пусть — разрешитель , работающий за полиномиальное время . , работающий как , но использующий вместо оракула . Его время работы ограничено сверху значением , что является полиномом (обращений к максимум ; на вход для можем подать максимум данных, так как больше сгенерить бы не успели). Значит, . |
Лемма: |
Класс замкнут относительно операций объединения, пересечения, конкатенации, замыкания Клини и дополнения. Если , то: , , , и . |
Доказательство: |
Докажем замкнутость замыкания Клини. Остальные доказательства строятся аналогично. Пусть — разрешитель , работающий за полиномиальное время. Построим разрешитель для языка .Худшая оценка времени работы разрешителя //позиции, где могут заканчиваться слова, принадлежащие for ( ) for ( ) if ( ) { if ( ) return true } return false равна , так как в множестве может быть максимум элементов, значит итерироваться по множеству можно за , если реализовать его на основе битового массива, например; при этом операция добавления элемента в множество будет работать за . Итого, разрешитель работает за полиномиальное время (так как произведение полиномов есть полином). Значит . |
Соотношение классов Reg и P
Теорема: |
Класс регулярных языков входит в класс , то есть: . |
Доказательство: |
Замечание. — ограничение и по времени, и по памяти. |
Соотношение классов CFL и P
Теорема: |
Класс контекстно-свободных языков входит в класс , то есть: . |
Доказательство: |
Первое включение выполняется благодаря существованию алгоритма Эрли. |
Примеры задач и языков из P
Класс задач, разрешимых за полиномиальное время достаточно широк, вот несколько его представителей:
- определение связности графов;
- вычисление наибольшего общего делителя;
- задача линейного программирования;
- проверка простоты числа.[2]
По теореме о временной иерархии существуют задачи и не из .