看板 [ Grad-ProbAsk ]
討論串[理工] 演算法 NP-complete證明
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[理工] 演算法 NP-complete證明
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者NTUmaki (西木野真姬)時間3年前 (2020/08/31 23:07), 編輯資訊
1
3
0
內容預覽:
有爬過文了，不懂的點差不多，但舊的那篇還是看不懂. 第一個是 vertex cover 問題. https://i.imgur.com/hb4qJE9.jpg. https://i.imgur.com/UfzNTcV.jpg. 主要在證 alpha iff beta (instance)那邊有問題.
(還有663個字)
#2
Re: [理工] 演算法 NP-complete證明
推噓5(5推 0噓 29→)留言34則，0人參與, 3年前最新作者mi981027 (呱呱竹)時間3年前 (2020/09/01 11:15), 3年前編輯資訊
0
3
0
內容預覽:
看完兩個問題後，我覺得兩個問題的癥結點差不多. 關鍵在於，我們如果想證明某個問題B是NP-hard. 要做的是，找到一個已知的NP-Complete問題 A，再證明A沒有比B難（B沒有比A簡單. ）. 怎麼證明A沒有比B難？. 想法上是：說明“若B可解，則A也可以解”. 這邊因果關係要分清楚，關鍵在
(還有1327個字)
首頁
上一頁
1
下一頁
尾頁