Изменения

Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>\mathrm{P}</tex> и <tex>\mathrm{NP}</tex><ref>[[Недетерминированные вычисления. Классы NP и Σ₁]]</ref>, не разрешенный по сей день.

Легко показать, что, по определению <tex>\mathrm{P}</tex>, <tex> \mathrm{P }\subset \mathrm{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>\mathrm{NP}</tex>.