Сложностью функции , вычисляемой некоторой машиной Тьюринга, называется функция , зависящая от длины входного слова и равная максимуму времени работы машины по всем входным словам фиксированной длины:
Если для функции f существует машина Тьюринга M такая, что для некоторого числа c и достаточно больших n, то говорят, что она принадлежит классу FP, или полиномиальна по времени.
Класс P является одним из фундаментальных в теории сложности вычислений.