計算理論

P-complete問題

CIRCUIT VALUE
已知一circuit，及每個輸入的truth value，求output是否為true

MONOTONE CIRCUIT VALUE
monotone circuit：當一個input由false變true，circuit的output不會由true變false

MAXIMUM FLOW 最大流

NP-complete問題

邏輯

SAT
3-SAT
MAX2SAT
NAESAT

圖論

獨立集
NODE COVER
CLIQUE
MAX-CUT
MAX BISECTION
BISECTION WIDTH
HAMILTON PATH
TSP(D)
2-COLORING
k-COLORING, k≧3

其他

TRIPARTITE MATCHING
SET COVERING
SET PACKING
EXACT COVER by 3-SET
KNAPSACK
BIN PACKING
INTEGER PROGRAMMING

書籍