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

отмена правки 71835269 участника 85.15.110.109 (обс)
(отмена правки 71835269 участника 85.15.110.109 (обс))
=== Класс NP ===
{{main|класс NP}}
[[Класс NP]] содержит задачи, которые [[недетерминированная машина Тьюринга]] в состоянии проверитьрешить за полиномиальное количество шагов от размера входных данных. Их решение может быть проверено детерминированной машиной Тьюринга за полиномиальное количество шагов. Следует заметить, что недетерминированная машина Тьюринга является лишь абстрактной моделью, в то время как современные компьютеры соответствуют [[Машина Тьюринга|детерминированной машине Тьюринга]] с ограниченной памятью. Поскольку [[детерминированная машина Тьюринга]] может рассматриваться как специальный случай [[недетерминированная машина Тьюринга|недетерминированной машины Тьюринга]], класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (то есть неэффективные для больших входов). В класс NP входят многие знаменитые проблемы, такие как [[задача коммивояжёра]], [[задача выполнимости булевых формул]], [[факторизация]] и др.
 
=== Проблема равенства классов P и NP ===