Вычислительная сложность: различия между версиями

Перейти к навигации Перейти к поиску
Нет описания правки
(оформление)
В частности, теория сложности вычислений определяет [[NP-полная задача|NP-полные задачи]], которые [[недетерминированная машина Тьюринга]] может решить за [[класс P|полиномиальное время]], тогда как для [[Детерминированная машина Тьюринга|детерминированной машины Тьюринга]] [[Равенство классов P и NP|полиномиальный алгоритм неизвестен]]. Обычно это сложные задачи оптимизации, например, [[Задача коммивояжёра|задача коммивояжёра]].
 
С [[теоретическая информатика|теоретической информатикой]] тесно связанные с такими областями как [[алгоритмический анализ]] и [[теория вычислимости]]. Связующим звеном между теоретической информатикой и алгоритмическим анализом является тот факт, что их формирование посвящено анализу необходимого количества ресурсов определённых алгоритмов решения задач, тогда как более общим вопросом является возможность использования алгоритмов для подобных задач. Конкретизируясь, попытаемся классифицировать проблемы, которые могут или не могут быть решены при помощи ограниченных ресурсов. СильноСильное ограничение доступных ресурсов отличает вычислительную сложность от вычислительной теории, последняя отвечает на вопрос какие задачи, в принципе, могут быть решены алгоритмически.
 
== Временная и пространственная сложности ==
Анонимный участник

Навигация