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