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