推 LPH66:其實標題沒錯, NP 問題是可驗證而已 06/02 18:37
→ DJWS:啊 你說的對 P問題屬於NP問題 / 應該要說標題下的不精準 06/02 22:23
※ 引述《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