315
правок
Изменения
м
Нет описания правки
Я этого не могу найти, но, казалось бы, это очевидно. Поэтому — отсебятина:
Любая задача из NP сводима по Карпу ({{TODO|t=тут, наверное, нужно написать про то, что за полином и почему}}) к любой задаче из NPC, поэтому, если задача из NPC решается за полином, то после сведения мы сможем решить за полином и любую задачу из NP.
== Соотношение между P, NP, PS ==
