※ 引述《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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1401664867.A.DCE.html ※ 編輯: DJWS (111.250.72.194), 06/02/2014 07:42:17