Re: [新聞] 數學史上新突破！人類發現史上最大質數有2233萬位數消失

看板Gossiping作者時間8年前 (2016/01/23 03:24), 編輯推噓11(11推 0噓 25→)
留言36則, 10人參與, 最新討論串10/10 (看更多)
有人推文說這是 NPhard 問題，但我認為不是 小弟以前的論文就是解 NPhard 的問題，只要問題是被歸類為 NPhard問題 就必須要用啟發式演算法來逼近求解，而且有可能不是最佳解 NPhard有個特性，那就是問題的難度越難時，他的求解時間會成指數成長 不會是線性成長，而且問題越複雜，數學式子越難列出來 NPhard問題比較典型的，而且常看到的問題 1. 背包問題：怎麼塞東西會是最有效率，這類問題可以衍生為 "貨櫃的裝箱問題"，貨物怎麼裝才能達到最大效率 2. 學校排課問題：這種問題牽扯到老師和學生的時間，教室的限制，教室的數量 等等...如果是要排簡單的幾間教室，幾堂課倒還好，很容易就可以列出數學式 丟到裡面求得最佳解。但像大學那種，幾乎不太可能用電腦幫你求解 因為複雜度會呈指數成長，所以只能用人腦去排課 3. 交通運輸路線問題 等等，不計其數.... 話說回來小弟的論文，小弟的論文是求解供應鏈最佳化模型 有兩萬個方程式，12萬個變數...我只能用類神經網路這種啟發式演算法去求解 要用目標式、限制式去算....電腦大概算 100 年也算不出來... 以上... ※ 引述《coolbetter33 (香港3345678)》之銘言： : 安安.鍵盤數學家來說理了. : 其實梅森質數統御可表示的最大質數很久了.其中最主要的原因是.有一套固定的模式來去 : 找它.叫做"盧卡斯-萊默檢驗法".從1952年以來都是用它來破紀錄.參考"梅森質數列表" : https://zh.wikipedia.org/zh-tw/%E6%A2%85%E6%A3%AE%E7%B4%A0%E6%95%B0 : 檢驗的原理 http://imgur.com/a/YuJvP : 發現規則了嗎?從4開始.平方減二再去跟M_p做同餘.迴圈loop.做到0為止.但是最多做 : p-1次. 交給資工的.一直跑程式就gg了.很難嗎?還好吧.目前找到p=74207281. : 要找一定還有啦.時間問題而已.下一個找到的會是你嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.204.23.72 ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1453490693.A.A98.html
推
01/23 03:26, , 1F
數學系是你??
01/23 03:26, 1F
→
01/23 03:28, , 2F
這個問題其實想玩的豬公豬哥遠多於數學系的
01/23 03:28, 2F
推
01/23 03:29, , 3F
很多非資工的都會以為這種東西給電腦跑運算就好了
01/23 03:29, 3F
→
01/23 03:30, , 4F
上過演算法就知道 "問題沒有這麼簡單"
01/23 03:30, 4F
推
01/23 03:31, , 5F
ㄎㄎ...會跑不完XD
01/23 03:31, 5F
→
01/23 03:34, , 6F
可能會跑完→可能跑到電腦關完機或當完機結果都還出不來
01/23 03:34, 6F
→
01/23 03:45, , 7F
所以論文寫完了嗎
01/23 03:45, 7F
推
01/23 03:59, , 8F
當然是P 只要驗證 n是否是質數 拿2到sqrt（n）都除一遍就
01/23 03:59, 8F
→
01/23 03:59, , 9F
好 複雜度是O(sqrt(n)),質數篩才是NP orNP complete
01/23 03:59, 9F
→
01/23 03:59, , 10F
質數問題跟本不在P或NP,是即使你有多項式時間內的解法 對
01/23 03:59, 10F
推
01/23 04:01, , 11F
於太大的n還是太大了
01/23 04:01, 11F
推
01/23 04:03, , 12F
NP Hard: 所有 NP 問題皆可在 polynomial time 轉化為該
01/23 04:03, 12F
→
01/23 04:03, , 13F
問題的個例, 所以只要在任一個 NP Hard 問題有 (determin
01/23 04:03, 13F
→
01/23 04:03, , 14F
istic) polynomial time 解, 全部 np 問題皆有 p 解. NP
01/23 04:03, 14F
→
01/23 04:03, , 15F
complete 為 NP 與 NP 的交集
01/23 04:03, 15F
→
01/23 04:07, , 16F
回orze04：問題是n如果用當代二進位表示的記憶體或硬碟存
01/23 04:07, 16F
→
01/23 04:08, , 17F
，所佔空間大約是O(\log n)，換言之應該要用所佔空間來比
01/23 04:08, 17F
→
01/23 04:09, , 18F
，否則這篇文章提到的背包問題早就變得不是難題喔XD
01/23 04:09, 18F
推
01/23 04:13, , 19F
log n還是比n小啊
01/23 04:13, 19F
→
01/23 04:13, , 20F
還有判斷某個正整數是不是質數，跟把某個正整數的質因數
01/23 04:13, 20F
→
01/23 04:14, , 21F
分解，除非某個正整數就是質數，否則難度有差喔！
01/23 04:14, 21F
→
01/23 04:15, , 22F
你令m=\log n然後塞回O(sqrt(n))，就不是多項式時間吧？
01/23 04:15, 22F
推
01/23 04:17, , 23F
背包問題是靠北在硬幹的話 在worst case中可能把大半排列
01/23 04:17, 23F
→
01/23 04:17, , 24F
組合都跑過
01/23 04:17, 24F
→
01/23 04:18, , 25F
問題是每個背包最大承受重量在現今電腦系統仍用二進位存
01/23 04:18, 25F
→
01/23 04:19, , 26F
n/2,n/3,n/4…n/sqrt(n)
01/23 04:19, 26F
→
01/23 04:20, , 27F
不要去管分母是質數或合數 反正只要看餘數就好
01/23 04:20, 27F
→
01/23 04:22, , 28F
(這時衡量運算速度，應該用儲存空間大小)
01/23 04:22, 28F
→
01/23 04:27, , 29F
(但很不幸除非量子電腦普及還是得用二進位而非任意n進位)
01/23 04:27, 29F
→
01/23 04:35, , 30F
(http://goo.gl/TNZvtA剛好有你說的情況，沒有騙你吧？)
01/23 04:35, 30F
推
01/23 04:37, , 31F
不懂O（log2(n)）也還是比O(n)小啊
01/23 04:37, 31F
→
01/23 04:39, , 32F
或許直接看http://goo.gl/TNZvtA吧
01/23 04:39, 32F
推
01/23 04:40, , 33F
歐 了解了 謝謝
01/23 04:40, 33F
→
01/23 11:08, , 34F
解出 np不等於 p再出來叫我，困
01/23 11:08, 34F
→
01/23 13:00, , 35F
以orz的說法質因數分解也是P了 那RSA早被破了
01/23 13:00, 35F
推
01/23 14:06, , 36F
單位是log(n)去看 試除法是指數時間 喜憨兒
01/23 14:06, 36F
‣ 更多 OxfordGOD 的文章
文章代碼(AID): #1Mee85gO (Gossiping)
討論串 (同標題文章)
完整討論串 (本文為第 10 之 10 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共10篇)
‣ 更多 OxfordGOD 的文章
文章代碼(AID): #1Mee85gO (Gossiping)