算法減少

如果我有一個我已經證明屬於P的算法A，那麼這個算法是否也屬於NPC類，還是嚴格P？ NP呢？ P屬於NP對嗎？算法減少

Thx任何幫助！

/Marthin

2010-05-22 Marthin

難道不是問題還是更嚴格的屬於P或NP或NPC的決策問題？算法有複雜性嗎？ – 2010-05-22 16:14:02

我不明白你的問題？ – Marthin 2010-05-22 16:16:22

那麼我從來沒有學過計算機科學，所以我知道的是我能找到和閱讀的東西。我可能錯了。根據我在維基百科找到的定義，複雜性類是一組問題而不是算法。「例如，類NP是可以通過多項式時間的非確定性圖靈機解決的一組決策問題」。你有沒有看過一個非確定性圖靈機算法？我甚至不知道算法屬於NP類是什麼意思。該定義沒有提到算法。所以我在問這個問題。 – 2010-05-22 16:37:00

若P！= NP則P不是NPC的一個子集，其實他們不相交。如果P = NP，則P和NPC是相同的。所有的P算法都是NP的一部分。查看Wikipedia page瞭解更多信息，以及一張圖解，準確解釋你所問的內容。

如果你能證明P = NP，你將會非常有名。

來源

2010-05-22 16:09:38

謝謝澄清！ – Marthin 2010-05-22 16:12:27

P不是NPC的一個子集（我認爲這意味着NP完全）取決於是否P = NP。如果P！= NP，那麼P和NPC不會相交，否則它們是相同的！請澄清一下。 – 2010-05-22 18:53:28

@Moron，這是正確的。 – 2010-05-22 23:30:53

回答

相關問題