Класс P

---

В теории алгоритмов классом P (от англ. polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных). Класс P включён в более широкие классы сложности алгоритмов.

Алгоритм отождествляется с детерминированной машиной Тьюринга, которая вычисляет ответ по данному на входную ленту слову из входного алфавита ${\displaystyle \Sigma }$. Временем работы алгоритма ${\displaystyle T_{M}(x)}$ при фиксированном входном слове x называется количество рабочих тактов машины Тьюринга от начала до остановки машины. Сложностью функции ${\displaystyle f:\Sigma ^{*}\to \Sigma ^{*}}$, вычисляемой некоторой машиной Тьюринга, называется функция ${\displaystyle C:\mathbb {N} \to \mathbb {N} }$, зависящая от длины входного слова и равная максимуму времени работы машины по всем входным словам фиксированной длины:

Если для функции f существует машина Тьюринга M такая, что ${\displaystyle C_{M}(n)<n^{c}}$ для некоторого числа c и достаточно больших n, то говорят, что она принадлежит классу P, или полиномиальна по времени.

Согласно тезису Чёрча — Тьюринга, любой мыслимый алгоритм можно реализовать на машине Тьюринга. Для любого языка программирования можно определить класс P подобным образом (заменив в определении машину Тьюринга на реализацию языка программирования). Если компилятор языка, на котором реализован алгоритм, замедляет исполнение алгоритма полиномиально (то есть время выполнения алгоритма на машине Тьюринга меньше некоторого многочлена от времени выполнения его на языке программирования), то определения классов P для этого языка и для машины Тьюринга совпадают. Код на ассемблере допускает преобразование в машину Тьюринга с небольшим полиномиальным замедлением, а поскольку все существующие языки допускают компиляцию в ассемблер (опять же, с полиномиальным замедлением), то определения класса P для машин Тьюринга и для любого существующего языка программирования совпадают.

---