Изменения
Нет описания правки
В начале 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> — недетерминизму).
{{Определение
|definition=
{{Определение
|definition=
Оракул — программа <tex>A(x)</tex>, вычисляющая за <tex>O(1)</tex>времени, верно ли, что <tex>x \in A</tex>.
}}
Сложностный класс задач, решаемых алгоритмом из класса <tex>C</tex> с оракулом для языка <tex>A</tex>, обозначают <tex>C^A</tex>. Так же <tex>C</tex> называют сложностным классом с доступом к оракулу <tex>A</tex>.
Если <tex>A</tex> — это множество языков, то <tex>C^A =\bigcup\limits_{D \in A}C^D</tex>, где <tex>D</tex> — язык из <tex>A</tex>.
