Если у меня есть алгоритм A, который я доказал, принадлежит P, этот алгоритм также может принадлежать классу NPC или это строго P? Как насчет НП? P Прямо относится к NP?Сокращения алгоритмов
Thx за помощь!
/Marthin
Если P! = NP, то Р не является подмножеством NPC, на самом деле они не пересекаются. Если P = NP, то P и NPC одинаковы. Однако все алгоритмы P являются частью NP. Обратитесь к Wikipedia page за дополнительной информацией и диаграммой, которая объясняет, что именно вы спрашиваете.
Если вы можете доказать, что P = NP, вы будете очень знамениты.
Спасибо за разъяснение! – Marthin
P не является подмножеством NPC (я полагаю, что означает NP-Complete) зависит от того, является ли P = NP или нет. Если P! = NP, то P и NPC не пересекаются, в противном случае они одинаковы! Просьба уточнить это. – 2010-05-22 18:53:28
@Moron, это правильно. –
Не были ли проблемы или даже более жесткие решения, связанные с P или NP или NPC? Алгоритмы имеют сложность правильно? –
Я не понимаю ваш вопрос? – Marthin
Ну, я никогда не изучал информатику, поэтому то, что я знаю, это то, что я мог найти и прочитать. Я могу быть не прав. Согласно определению, которое я нашел, например, в Википедии, класс сложности представляет собой набор проблем, а не алгоритмов. «Например, класс NP представляет собой набор задач решения, которые могут быть решены недетерминированной машиной Тьюринга в полиномиальное время». Вы когда-нибудь видели алгоритм для недетерминированной машины Тьюринга? Я даже не знаю, что значит, что алгоритм принадлежит классу NP. В определении ничего не говорится об алгоритмах. Поэтому я спрашиваю об этом. –