Re: [其他] 見證奇蹟的時刻 NP=P

看板Math作者 (豔鵪鶉)時間12年前 (2013/06/01 01:45), 編輯推噓6(6推 0噓 29→)
留言35則, 8人參與, 6年前最新討論串3/5 (看更多)
我也想問一下很多人在問的問題，就是 如果真的証明P=NP了，對這個世界會造成什麼影響嗎@@? 我不是資訊或數學系的 對P、NP的了解大概也只有LPH66大大寫的那篇@@ 有個例子是說質因數太快被分解的話我們的密碼學會崩盤（沒會錯意吧..） 我在想，根據 Weierstrass Approximation Theorem 在閉區間中的連續函數都可以用多項式函數來近似 反過來看 對連續函數，都存在著"不會收斂比較快的多項式函數" 也就是說，即使証明了P=NP，或甚至P=全世界可解的問題 但找的到多項式解是一個不比原本演算法來得快的解法 這樣對這世界的進步是否也有限呢？ 那麼目標是否該是對問題找個簡單的解法（但這又回到沒系統性的一一擊破了..） 為何人類這幾十年來會執著於P=NP的証明上呢？ 真的滿好奇的，希望熟悉的大大解答@@ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.136.172.87
→
06/01 01:58, , 1F
"不比原本演算法快" 這個要看你的問題規模
06/01 01:58, 1F
→
06/01 01:58, , 2F
分別多項式時間跟指數時間 原因是消耗(時間)成長速率
06/01 01:58, 2F
→
06/01 01:59, , 3F
但是若給個什麼 O(n^(2^(65536))) 那的確沒辦法實用
06/01 01:59, 3F
→
06/01 01:59, , 4F
但是說不定有人就會找到有效率的演算法! (應該大家都
06/01 01:59, 4F
→
06/01 01:59, , 5F
想找到吧XD)
06/01 01:59, 5F
→
06/01 02:00, , 6F
不過理論中非常重要~
06/01 02:00, 6F
是的，我的疑問你大概也寫出來了 如果只証明了多項式解的存在卻沒說怎麼找，或者找到的多項式很不實用 （個人覺得如果真的被証出來，這兩者的機率都很大...） 那麼除了振奮人心外，在實際用途面似乎沒有多少影響@@? 不管P和NP是否相等，人們還是要一個一個去找有沒有更快的P解... 當然理論發展還是非常重要的，只是距離重要影響力的理論似乎還有一段? ※ 編輯: gj942l41l4 來自: 220.136.172.87 (06/01 02:29)
推
06/01 11:27, , 7F
你說的"目標"只有在P=NP的情況才有意義 如果P!=NP那
06/01 11:27, 7F
→
06/01 11:28, , 8F
我們就知道任何NP-complete的問題不可能有"有效率"的
06/01 11:28, 8F
→
06/01 11:29, , 9F
解法 當然效率的定義也是有模糊空間 一般討論複雜度
06/01 11:29, 9F
→
06/01 11:31, , 10F
都是只"最壞情況"而言 有許多類問題是目前任何演算法
06/01 11:31, 10F
→
06/01 11:34, , 11F
都有人設計出沒有效率的特例 但這些特例在現不太遇到
06/01 11:34, 11F
推
06/01 14:50, , 12F
考慮一下partition問題:把一個整數集合分成兩個不相
06/01 14:50, 12F
→
06/01 14:52, , 13F
交子集,使得其元素和相等.這問題是NPC,但現實世界裡
06/01 14:52, 13F
→
06/01 14:52, , 14F
用個普通的dynamic programming演算法就解得很快.那
06/01 14:52, 14F
→
06/01 14:54, , 15F
麼它為什麼是NPC? NPC理論牽涉到deterministic和
06/01 14:54, 15F
→
06/01 14:56, , 16F
nondeterministic兩種運算模型中,是否存在一條鴻溝,
06/01 14:56, 16F
→
06/01 15:04, , 17F
大部份的人現在認為,要解決這個問題,要有新的數學進
06/01 15:04, 17F
→
06/01 15:05, , 18F
展,就好像一些數學史上的難題,有些是發展了一套理論
06/01 15:05, 18F
→
06/01 15:05, , 19F
為了解難題而發展出了許多的理論,現在NPC問題有人的
06/01 15:05, 19F
→
06/01 15:07, , 20F
看法就是這樣,猜測它可能沒辦法很快解答
06/01 15:07, 20F
→
06/01 15:08, , 21F
不過好像也有人認為它是千禧年懸賞題裡會比較快解出
06/01 15:08, 21F
推
06/02 01:42, , 22F
講了半天 還是看不到P=NP 在生活中實際應用到底為何
06/02 01:42, 22F
→
06/02 01:46, , 23F
或許可以這麼說: P=NP雖然不能說是有重大實際應用的
06/02 01:46, 23F
→
06/02 01:47, , 24F
充分條件, 但至少是個必要條件
06/02 01:47, 24F
推
06/02 02:26, , 25F
對不起 看了LPH66大的文後 我想收回上面那推文
06/02 02:26, 25F
→
06/02 02:27, , 26F
大概曉得為什麼P=NP問題 會列在"千禧年大獎難題"首位
06/02 02:27, 26F
推
06/02 02:31, , 27F
P=NP太可怕了 雖然不是每件事或許實際應用不大
06/02 02:31, 27F
推
06/02 02:33, , 28F
P=NP太可怕了 雖然每件事或許實際應用不大...
06/02 02:33, 28F
→
06/02 02:34, , 29F
但很多事 都可以用多項式時間解掉 那真的很恐怖
06/02 02:34, 29F
→
06/02 13:20, , 30F
我正是在問這個用多項式解決的影響有多恐怖
06/02 13:20, 30F
→
06/02 13:20, , 31F
不過看來這是一個未來（可能的）根基 而真正造成影
06/02 13:20, 31F
→
06/02 13:21, , 32F
響需要仰賴後人更多的努力 理解沒錯的話是這樣吧
06/02 13:21, 32F
→
11/10 11:53, , 33F
我正是在問這個用多項式 https://noxiv.com
11/10 11:53, 33F
→
01/02 15:26, 7年前 , 34F
充分條件, 但至少是個 https://noxiv.com
01/02 15:26, 34F
→
07/07 11:06, 6年前 , 35F
用個普通的dynami https://muxiv.com
07/07 11:06, 35F
‣ 更多 gj942l41l4 的文章
文章代碼(AID): #1HgE7AiT (Math)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 3 之 5 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共5篇)
‣ 更多 gj942l41l4 的文章
文章代碼(AID): #1HgE7AiT (Math)