Изменения

Одним из центральных вопросов теории сложности является вопрос о равенстве классов <tex>P</tex> и [[NP]], не разрешенный по сей день. Однако легко  Легко показать, что по определению, <tex> P \subset NP</tex>, так как достаточно для любой задачи класса <tex>P</tex> привести ее решение в качестве сертификата, а значит задача по определению будет входить в класс <tex>NP</tex>