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