Re: [問題] 驗證某數是否為質數是NP問題
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間10年前 (2014/06/02 07:21)推噓1(1推 0噓 1→)留言2則, 2人參與討論串4/4 (看更多)
※ 引述《dharma (達)》之銘言：
: 前面大家的回應有點難懂
: 要慢慢研究
: 現在先換個簡單的問法
: A.
: 判別一個數是否為質數
這是P問題 (你的文章標題下錯了)
十年前才發現的，論文名稱是PRIMES is in P，是重大突破
該演算法後來被大家稱做AKS質數檢測法
就是前面板友回文提到的
: B.
: 不知81785036517是否為質數
: 但要確定277877是否為81785036517因數
: 可以直接拿去除
除法是P問題
長除法的時間複雜度是O(n^2)
http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations
請參考division那一欄
: 照直覺說
: 一個大數a，要確認它是不是質數
: 應該遠比確認b是不是a的因數難很多
你說的很對
: 那麼
: A應該比B困難啊
你說的很對
: 我哪裡誤解了
: thanks
你可以這樣想：
P問題的範圍非常非常大，
大到可以同時包含這兩個困難度不一樣的問題。
至於P究竟有多大，是不是跟NP一樣大？
這是當今的數學難題，還沒有人知道怎麼證明。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.72.194
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1401664867.A.DCE.html
※ 編輯: DJWS (111.250.72.194), 06/02/2014 07:42:17
推
06/02 18:37, , 1F
06/02 18:37, 1F
→
06/02 22:23, , 2F
06/02 22:23, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
