141
правка
Изменения
м
→Задача равенства P и NP: Ссылка на ДМТ и НМТ
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[NP]]</ref>, не разрешенный по сей день.
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая ДМТ<ref>[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]</ref>, которая является частным случаем [[Недетерминированные вычисления. Классы NP и Σ₁|НМТ]], а значит задача, по определению, будет входить в класс <tex>NP</tex>.
== Ссылки ==
<references/>
