editor
177
правок
Изменения
м
→Задача равенства P и NP
== Задача равенства P и NP ==
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[Недетерминированные вычисления. Классы NPи Σ₁]]</ref>, не разрешенный по сей день.
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 ДМТ], которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.
