211
правок
Изменения
м
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Недетерминированные вычисления. Классы NP и Σ₁|NP]] и т.д.
Нет описания правки
{{Определение
|definition=
