→ suhorng :"不比原本演算法快" 這個要看你的問題規模 06/01 01:58
→ suhorng :分別多項式時間跟指數時間 原因是消耗(時間)成長速率 06/01 01:58
→ suhorng :但是若給個什麼 O(n^(2^(65536))) 那的確沒辦法實用 06/01 01:59
→ suhorng :但是說不定有人就會找到有效率的演算法! (應該大家都 06/01 01:59
→ suhorng :想找到吧XD) 06/01 01:59
→ suhorng :不過理論中非常重要~ 06/01 02:00
是的，我的疑問你大概也寫出來了
如果只証明了多項式解的存在卻沒說怎麼找，或者找到的多項式很不實用
（個人覺得如果真的被証出來，這兩者的機率都很大...）
那麼除了振奮人心外，在實際用途面似乎沒有多少影響@@?
不管P和NP是否相等，人們還是要一個一個去找有沒有更快的P解...
當然理論發展還是非常重要的，只是距離重要影響力的理論似乎還有一段?
※ 編輯: gj942l41l4 來自: 220.136.172.87 (06/01 02:29)
推 recorriendo :你說的"目標"只有在P=NP的情況才有意義 如果P!=NP那 06/01 11:27
→ recorriendo :我們就知道任何NP-complete的問題不可能有"有效率"的 06/01 11:28
→ recorriendo :解法 當然效率的定義也是有模糊空間 一般討論複雜度 06/01 11:29
→ recorriendo :都是只"最壞情況"而言 有許多類問題是目前任何演算法 06/01 11:31
→ recorriendo :都有人設計出沒有效率的特例 但這些特例在現不太遇到 06/01 11:34
推 id010406 :考慮一下partition問題:把一個整數集合分成兩個不相 06/01 14:50
→ id010406 :交子集,使得其元素和相等.這問題是NPC,但現實世界裡 06/01 14:52
→ id010406 :用個普通的dynamic programming演算法就解得很快.那 06/01 14:52
→ id010406 :麼它為什麼是NPC? NPC理論牽涉到deterministic和 06/01 14:54
→ id010406 :nondeterministic兩種運算模型中,是否存在一條鴻溝, 06/01 14:56
→ id010406 :大部份的人現在認為,要解決這個問題,要有新的數學進 06/01 15:04
→ id010406 :展,就好像一些數學史上的難題,有些是發展了一套理論 06/01 15:05
→ id010406 :為了解難題而發展出了許多的理論,現在NPC問題有人的 06/01 15:05
→ id010406 :看法就是這樣,猜測它可能沒辦法很快解答 06/01 15:07
→ id010406 :不過好像也有人認為它是千禧年懸賞題裡會比較快解出 06/01 15:08
推 mo2 :講了半天 還是看不到P=NP 在生活中實際應用到底為何 06/02 01:42
→ kaifrankwind:或許可以這麼說: P=NP雖然不能說是有重大實際應用的 06/02 01:46
→ kaifrankwind:充分條件, 但至少是個必要條件 06/02 01:47
推 mo2 :對不起 看了LPH66大的文後 我想收回上面那推文 06/02 02:26
→ mo2 :大概曉得為什麼P=NP問題 會列在"千禧年大獎難題"首位 06/02 02:27
推 mo2 :P=NP太可怕了 雖然不是每件事或許實際應用不大 06/02 02:31
推 mo2 :P=NP太可怕了 雖然每件事或許實際應用不大... 06/02 02:33
→ mo2 :但很多事 都可以用多項式時間解掉 那真的很恐怖 06/02 02:34
→ gj942l41l4 :我正是在問這個用多項式解決的影響有多恐怖 06/02 13:20
→ gj942l41l4 :不過看來這是一個未來（可能的）根基 而真正造成影 06/02 13:20
→ gj942l41l4 :響需要仰賴後人更多的努力 理解沒錯的話是這樣吧 06/02 13:21