141
правка
Изменения
м
NP в tex'е и ref
== Задача равенства P и NP ==
Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и <tex>NP</tex><ref>[[NP]]</ref>, не разрешенный по сей день.
Легко показать, что, по определению <tex>P</tex>, <tex> P \subset NP</tex>, так как для любой задачи класса <tex>P</tex> существует соответствующая ДМТ, которая является частным случаем НМТ, а значит задача, по определению, будет входить в класс <tex>NP</tex>.
