→ sdfg014025xx: (A)NPC 是NPH和NP的交集 01/05 00:45
推 eggy1018: (B)要先有一組certificates,並在polynomial time verify 01/05 01:23
→ eggy1018: 才是NP 01/05 01:23
推 eggy1018: (C)不太確定 我覺得是NP-complete 可以互相reduce 的條 01/05 01:25
→ eggy1018: 件 01/05 01:25
推 eggy1018: (E)反過來了，因為可以reduce到SAT表示SAT比較原問題難 01/05 01:27
→ eggy1018: 解，此時仍沒辦法知道原問題多難，所以不能確定原問題NP 01/05 01:27
→ eggy1018: -complete, 反過來才有辦法說明～ 01/05 01:27
→ eggy1018: 以上有錯 還麻煩各位大大指正了 01/05 01:27
推 FRAXIS: (C) NPH 可能比 NPC 難 所以不一定可以 reduce 01/05 03:09