83
правки
Изменения
м
Нет описания правки
* поиск диаметра связного графа
Но существуют и задачи не из '''P''', по [[теорема о временной иерархии|теореме о временной иерархии]], существуют и задачи, работающие за более чем <tex>p(x) \in Poly</tex>, а значит не входящие в объединение <tex>\bigcup_{i=0}^{\infty} DTIME(in^i)</tex>, что и требовалось показатьиз '''P'''.
==Задача равенства '''P''' и '''NP'''==
Основополагающей задачей теории сложности является задача равенства классов '''P''' и [[NP]], не разрешенная по сей день. Однако легко показать, что по определению, <tex> P \subset NP</tex>, так как достаточно для любой задачи класса '''P''' привести ее решение в качестве сертификата, а значит задача по определению будет входить в класс '''NP'''
