Изменения
Нет описания правки
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964), и Эдмнодса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Недетерминированные вычисления. Классы NP и Σ₁|NP]] и т.д.
Для начала введем понятия <tex>DTIME</tex> и <tex>DSPACE</tex>, аналогичным образом определяются классы <tex>NSPACE</tex> и <tex>NTIME</tex> (префикс <tex>D</tex> соответствует детерминизму, а <tex>N</tex> — недетерминизму).
