推 jameschou:NP complement就是NP hard裡面為NP的問題 所以他們交集 01/19 23:17
→ jameschou:的部份就是整個 NP complement的部份 01/19 23:18
→ aoqq12:所以有些np取complement 會屬於np hard 有些屬於npc 01/19 23:23
→ aoqq12:感覺起來好奇怪= =a 我想問一下 01/19 23:23
※ 編輯: aoqq12 來自: 123.204.152.191 (01/19 23:26)
推 jameschou:........ 我跟著你打 看錯了= =... 我以為是NP complete 01/19 23:27
→ jameschou:我對不起你= = 01/19 23:28
→ aoqq12:驚 = =" 01/19 23:28
→ aoqq12:不過 感覺上好像有道理的樣子= =a 01/19 23:31
→ aoqq12:不然也不知道他交集在哪 01/19 23:31
→ jameschou:問題是在co-np的定義 其實他定義不是非-NP 01/19 23:32
→ aoqq12:不然他是指? 01/19 23:33
→ jameschou:一個問題是co-np <=> 這個問題的complement必在複雜度NP 01/19 23:34
→ aoqq12:所以例如vertex cover的問題 01/19 23:37
→ aoqq12:如果取 complement 他還是個np問題 01/19 23:37
→ aoqq12:complement只是反向的結果的意思 01/19 23:37
※ 編輯: aoqq12 來自: 123.204.152.191 (01/19 23:41)
→ jameschou:我覺得complement的意思是類似反意的意思耶@@ 01/19 23:40
→ jameschou:就是 一個題目 你可以找到反例 然後找反例的時間是NP 01/19 23:41
→ jameschou:他有個例子不錯: 給有限的整數集,是否"每個"非空子集都 01/19 23:44
→ aoqq12:!!! 維基寫的還蠻詳細的 感謝!! 01/19 23:44
→ jameschou:能找到一個非零和? 01/19 23:45
→ aoqq12:原來維基也能這樣用= = 01/19 23:46
→ aoqq12:所以應該是照你說的反例的意思 01/19 23:47
→ aoqq12:感謝 orz 01/19 23:47