判斷題任何圖的二著色問題都是NPC問題。

您可能感興趣的試卷

你可能感興趣的試題

1.多項選擇題NP完全問題的證明方法有()

A.限制技術
B.分支設計
C.局部替換
D.定義法

2.多項選擇題以下關于判定問題難易處理的敘述中正確的是()

A.需要超過多項式時間算法求解的問題是易處理的
B.可以由多項式時間算法求解的問題是易處理的
C.需要超過多項式時間算法求解的問題是不能處理的
D.可以由多項式時間算法求解的問題是難處理的

3.多項選擇題下面屬于NP完全問題的是()

A.最小頂點覆蓋
B.SAT
C.最大獨立集
D.旅行商問題