[理工] [algo] np co-np

看板Grad-ProbAsk作者 (阿任)時間15年前 (2011/01/19 23:01), 編輯推噓2(2推 0噓 23→)
留言25則, 3人參與, 最新討論串1/1
我想問一下 為什麼 np 跟co-np有交集 而不是兩個獨立的? co-np 為np complement 要怎麼形容他們的關係? 有交集的部份是? 哪部份 = =a 還有個問題 如果以決定性問題來說 取complement 就是如果答案是yes的 在complement就為no yes 跟 no 不是應該沒交集嗎? 還是說他是指找出yes 找出no的方法? 我搞不太懂這意思 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.204.152.191 ※ 編輯: aoqq12 來自: 123.204.152.191 (01/19 23:10)
推
01/19 23:17, , 1F
NP complement就是NP hard裡面為NP的問題 所以他們交集
01/19 23:17, 1F
→
01/19 23:18, , 2F
的部份就是整個 NP complement的部份
01/19 23:18, 2F
→
01/19 23:23, , 3F
所以有些np取complement 會屬於np hard 有些屬於npc
01/19 23:23, 3F
→
01/19 23:23, , 4F
感覺起來好奇怪= =a 我想問一下
01/19 23:23, 4F
※ 編輯: aoqq12 來自: 123.204.152.191 (01/19 23:26)
推
01/19 23:27, , 5F
........ 我跟著你打 看錯了= =... 我以為是NP complete
01/19 23:27, 5F
→
01/19 23:28, , 6F
我對不起你= =
01/19 23:28, 6F
→
01/19 23:28, , 7F
驚 = ="
01/19 23:28, 7F
→
01/19 23:31, , 8F
不過 感覺上好像有道理的樣子= =a
01/19 23:31, 8F
→
01/19 23:31, , 9F
不然也不知道他交集在哪
01/19 23:31, 9F
→
01/19 23:32, , 10F
問題是在co-np的定義 其實他定義不是非-NP
01/19 23:32, 10F
→
01/19 23:33, , 11F
不然他是指?
01/19 23:33, 11F
→
01/19 23:34, , 12F
一個問題是co-np <=> 這個問題的complement必在複雜度NP
01/19 23:34, 12F
→
01/19 23:37, , 13F
所以例如vertex cover的問題
01/19 23:37, 13F
→
01/19 23:37, , 14F
如果取 complement 他還是個np問題
01/19 23:37, 14F
→
01/19 23:37, , 15F
complement只是反向的結果的意思
01/19 23:37, 15F
※ 編輯: aoqq12 來自: 123.204.152.191 (01/19 23:41)
→
01/19 23:40, , 16F
我覺得complement的意思是類似反意的意思耶@@
01/19 23:40, 16F
→
01/19 23:41, , 17F
就是 一個題目 你可以找到反例 然後找反例的時間是NP
01/19 23:41, 17F
→
01/19 23:42, , 18F
我剛看了一下維基 http://en.wikipedia.org/wiki/Co-NP
01/19 23:42, 18F
→
01/19 23:44, , 19F
他有個例子不錯: 給有限的整數集,是否"每個"非空子集都
01/19 23:44, 19F
→
01/19 23:44, , 20F
!!! 維基寫的還蠻詳細的 感謝!!
01/19 23:44, 20F
→
01/19 23:45, , 21F
能找到一個非零和?
01/19 23:45, 21F
→
01/19 23:46, , 22F
原來維基也能這樣用= =
01/19 23:46, 22F
→
01/19 23:47, , 23F
所以應該是照你說的反例的意思
01/19 23:47, 23F
→
01/19 23:47, , 24F
感謝 orz
01/19 23:47, 24F
→
09/11 14:09, , 25F
原來維基也能這樣用= https://daxiv.com
09/11 14:09, 25F
‣ 更多 aoqq12 的文章
文章代碼(AID): #1DDlovH1 (Grad-ProbAsk)