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