看板 [ Prob_Solve ]
討論串[問題] 驗證某數是否為質數是NP問題
共 4 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 驗證某數是否為質數是NP問題
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者dharma (達)時間10年前 (2014/06/01 10:54), 編輯資訊
1
0
1
內容預覽:
看了許多P和NP資料. 怪怪的. 例如下面這兩個例子. 1.. 判別一個數是否為質數是一個「P問題」. 2.. 不知81785036517是否為質數. 但要確定277877是否為81785036517因數. 可以直接拿去除. 針對277877來驗證8178503651是否為質數的動作. 可在多項式時
(還有86個字)
#2
Re: [問題] 驗證某數是否為質數是NP問題
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者johnathan717 (好神公仔)時間10年前 (2014/06/01 11:52), 10年前編輯資訊
0
0
2
內容預覽:
如果已經知道要驗證的是什麼數. 那麼就可以deterministic在多項式時間完成，所以問題1是P. 一個問題是NP的意思是說. 你可以nondeterministic地在多項式時間驗證答案是"Yes". 例如要判斷一個數是不是合數，因為我可以nondeterministic猜出他的因數. 再用多
(還有175個字)
#3
Re: [問題] 驗證某數是否為質數是NP問題
推噓2(2推 0噓 4→)留言6則，0人參與, 最新作者dharma (達)時間10年前 (2014/06/01 18:01), 10年前編輯資訊
1
0
2
內容預覽:
前面大家的回應有點難懂. 要慢慢研究. 現在先換個簡單的問法. A.. 判別一個數是否為質數. B.. 不知81785036517是否為質數. 但要確定277877是否為81785036517因數. 可以直接拿去除. 照直覺說. 一個大數a，要確認它是不是質數. 應該遠比確認b是不是a的因數難很多.
(還有66個字)
#4
Re: [問題] 驗證某數是否為質數是NP問題
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者DJWS (...)時間10年前 (2014/06/02 07:21), 10年前編輯資訊
0
0
2
內容預覽:
這是P問題 (你的文章標題下錯了). 十年前才發現的，論文名稱是PRIMES is in P，是重大突破. 該演算法後來被大家稱做AKS質數檢測法. 就是前面板友回文提到的除法是P問題. 長除法的時間複雜度是O(n^2). http://en.wikipedia.org/wiki/Computati
(還有165個字)
首頁
上一頁
1
下一頁
尾頁