Алгоритм сокращения

Question

Если у меня есть алгоритм A, который, как я доказал, принадлежит P, может ли этот алгоритм также принадлежать к классу NPC или он строго P? А как насчет NP? P принадлежит NP, верно?

Спасибо за любую помощь!

/ Marthin

Answer 1

Если P! = NP, то P не является подмножеством NPC, фактически они не пересекаются.Если P = NP, то P и NPC одинаковы.Все P алгоритмы являются частью NP, хотя.Посетите страницу Википедии для получения дополнительной информации и диаграммы, которая точно объясняет, что вы спрашиваете.

Если вы сможете доказать, что P = NP, вы будете очень известны.