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