Класс Р - (от англ. polynomial) — множество задач распознавания, которые могут быть решены на детерминированной машине Тьюринга за полиномиальное от длины входа время. Аналогично, для задач поиска определяется класс FP (от англ. functional polynomial).
Более формально, рассмотрим детерминированные машины Тьюринга, которые вычисляют ответ по данному на входную ленту слову из входного алфавита . Временем работы машины Тьюринга при фиксированном входном слове x называется количество рабочих тактов машины Тьюринга от начала до остановки машины.