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

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