问题
1. SAT问题
问题P为若干个子句的逻辑与,每个子句是若干变量的逻辑或(P是合取范式/CNF),问是否存在一组输入,使得P为真。
根据对偶性,这一问题可以表述为:命题S是若干子句的逻辑或,每个子句是若干变量的逻辑与(S是析取范式/DNF),问S是否为恒真命题。
2. 01整数规划
给定整数矩阵C和整数向量d,问是否存在01向量x使得[latex]Cx\geq d[/latex].
注:似乎Karp原论文中此处把“大于等于”误为“等于”:
https://cs.stackexchange.com/questions/19716/0-1-integer-progr[……]