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

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