? asked in 教育與參考其他:教育 · 1 decade ago

NP-Complete的意思?

請幫我明確解釋NP-Complete的意思!!

還有請靠訴我他在數學屬於什麼樣的難度??

給您20點

1 Answer

Rating
  • May
    Lv 4
    1 decade ago
    Favorite Answer

    Cobham和Eomond首先指出,不同的演算法有不同的時間複雜度(time complexity),一些針對well-defined 問題所發展出來的演算法,有些屬於「多項式時間演算法」(polynomial time algorithms),有些則是「指數時間演算法」(exponential time algorithms)。對於後者,當問題的複雜度加大時,會使得該些演算法的演算時間呈指數成長,導致求得解答所需的時間可能需花費數年,甚至數世紀或更長時間。之後,Cook提出「NP-complete 理論」,從此證實了運用資訊科技演算法求解也存在時間限制。

    NP: 可以用 non-deterministic machine 在 polynomial 數量的計算時間內解決的 decision problem。這類的問題只要給個解答,可以很快地驗證出這個解答是否正確。

    NP-complete 是指那些最困難的 NP 問題。只要是 NP-complete 的問題,也就是被認為「不太可能」有 P 解法的問題。這種類型的問題的特點在於,只要一個 NP-complete 問題找到 P 的解法,其他屬於 NP-complete 的問題也能一併找到 P 的解法。

    最有名的例子就是 subset-sum 這個問題。這個問題就是給一堆整數,問你說能不能從這堆整數裡挑一些來而且讓他們加起來等於零。以這個問題為例,如果告訴你一組答案的話,請你驗證這組答案是對或錯,很快就可以知道結果。但是要請你找自行出一組「正確、的答案,則除了逐一去測試所有的數字組合並確認是否符合要求之外,好像沒有其他更有效率的做法。

    可以參考這各網頁的說明歐~

    http://www.pws.stu.edu.tw/bangye/otherpaper/NPC1-b...

    Source(s): 網路
Still have questions? Get your answers by asking now.