Белгілі бір уақыт пен кеңістікті пайдаланып, мәселені шешудің не екенін нақты анықтау үшін, детерминистік Тьюринг машинасы сияқты есептеу моделі қолданылады. Детерминистік Тьюринг машинасының M x кірісіне қажетті уақыт - бұл машина тоқтамай, жауап ('иә' немесе 'жоқ') шығаруға дейін жасаған жағдайлардың жалпы саны немесе қадамдар саны. M Тьюринг машинасы f (n) уақыт ішінде жұмыс істейді, егер әрбір n n ұзақтықтағы әрбір кіріс M-дің талап еткен f (n) ең көп уақыты болса. Егер мәселені шешу үшін f (n) уақытында жұмыс істейтін Тьюринг машинасы болса, онда A шешім проблемасы f (n) уақытында шешілуі мүмкін. Күрделілік теориясы проблемаларды қиындыққа қарай жіктеуге байланысты болғандықтан, кейбір критерийлер негізінде проблемалар анықталады. Мысалы, детерминистік Тьюринг машинасындағы f (n) уақыт ішінде шешілетін проблемалар жиынтығы DTIME (f (n)) -пен көрсетіледі.
Детерминистік Тьюринг машинасында уақытпен шешілетін кез келген белгілі серияны сипаттау үшін қолданылатын термин қандай?
DTIME (f (n)) 