P

Если время выполнения, заданное как функция длины входа, описывается полиномом, то говорится, что алгоритм имеет полиномное время выполлнения. Алгоритмы с полиномным временем выполнения являются суб-экспоненциальными, но не все суб-экспоненциальные алгоритмы имеют полиномное время выполнения; пример - e**(p*x) [Криптографический словарь Карэна Исагулиева - www.racal.ru]

Если Вы считаете, что в описании термина "P" есть ошибка, пожалуйста, сообщите нам.