→ Favonia :是「不知道是不是 NP-hard」而不是「不是 NP-hard」 04/03 23:16
推 wsx02 :謝謝 04/03 23:37
終於看到計算理論的文章了(很感動)
首先MINCUT屬於P, 看來原PO也認同
而 P = coP 因為 P 是 deterministic class
而 P 包含於 NP, coP 包含於 coNP,
所以答案要選 ABCD.
選到 NP-complete 就太誇張了,
NP-complete = NP-Hard 與 NP 的交集,
MINCUT並不是 NP-Hard.
※ 引述《wsx02 ()》之銘言：
: choose all and only those complexity classes that are known to contain the
: corresponding MINCUT decision problem
: (A)P (B)co-P (C)NP (D)co-NP (E)NP-complete
: 我想這個問題跟找max flow一樣
: 可以在P內解決
: 所以一定有A
: 可是我看不太懂題意 是說只要包含P就要選嗎?
: 是不是要選ABCD?
: 另外我在書上沒看到co-P跟co-NP這兩個名詞..請問這兩個是什麼..
: google自己得到的結果是 co-P是非P, co-NP是非NP, 這樣的理解是對的嗎?
: 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.46
補一下 P = coP 的說明:
If L is in P, then for all x, there exists a polynomial time TM M,
such that M(x) = yes if x is in L, and M(x) = no if x is not in L.
Since L is in P, L' is in coP. L' can be shown in P by consturcting a TM M',
M'(x) = yes if M(x) = no, i.e. x is not in L and is therefore in L';
M'(x) = no if M(x) = yes, i.e. x is in L and is therefore not in L'.
※ 編輯: robertshih 來自: 140.112.30.46 (04/03 23:08)