C++ 子集相等性是NP完全的问题

子集对应，又称为“子集总和”问题，是一个经典的NP完全计算问题。给定一组数字和一个目标值，任务是确定是否存在一个子集的数字总和等于目标值。该问题的NP完全性源于它能够通过多项式时间的规约解决各种其他NP完全问题。尽管它的定义很简单，但目前没有已知的有效算法能够解决所有实例的“子集对应”问题，因此它在理论计算机科学和优化领域具有重要的研究价值，并在密码学、资源分配和动态问题等多个领域有实际应用。

使用的方法

• 从子集求和问题进行规约

• 从3SAT进行规约

从子集求和问题进行规约

证明“子集相等性”是NP完全的一种方法是通过从著名的NP完全问题“子集总和”进行规约。

步骤

• 给定一个“子集总和”问题的实例，其中包含一组整数S和一个目标值T。

• 创建一个具有相同集合S和目标值2T的“子集相等性”问题的实例。

• 如果在“子集总和”问题中存在一个子集的总和等于T，则在“子集相等性”问题中存在一个子集的总和等于2T，通过将相同的子集与自身相加得到。

• 假设在“子集总和”问题中不存在一个子集的总和等于T，则在“子集相等性”问题中也不存在一个子集的总和等于2T，因为任何总和小于2T的子集与自身相加都不会超过2T。

• 这个规约证明了解决“子集相等性”问题与解决“子集总和”问题一样困难，使其成为NP完全问题。

示例

#include <iostream>
#include <vector>
using namespace std;

bool isSubsetSum(vector<int>& set, int n, int sum) {
   if (sum == 0) return true;
   if (n == 0) return false;

   if (set[n - 1] > sum) return isSubsetSum(set, n - 1, sum);

   return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]);
}

bool isSubsetAggregateReduction(vector<int>& set, int n, int sum) {
   return !isSubsetSum(set, n, sum) && !isSubsetSum(set, n, 2 * sum);
}

int main() {
   vector<int> set = {3, 34, 4, 12, 5, 2};
   int sum = 18; 
   if (isSubsetAggregateReduction(set, set.size(), sum)) {
      cout << "No subset exists in Subset Aggregate issue that sums to " << sum << " and no subset exists that sums to " << 2 * sum << " by adding the same subset with itself." << endl;
   } else {
      cout << "There exists a subset in Subset Aggregate issue that sums to " << sum << " or a subset in Subset Equity issue that sums to " << 2 * sum << " by adding the same subset with itself." << endl;
   }

   return 0;
}

输出

There exists a subset in Subset Aggregate issue that sums to 18 or a subset in Subset Equity issue that sums to 36 by adding the same subset with itself.

3SAT问题的规约

另一种方法是通过将3SAT问题直接减小为另一个已知的NP完全问题，例如“子集对应问题”，来证明“子集对应问题”是NP完全问题。

步骤

• 给定一个3SAT问题的实例，该问题由一个布尔方程组成，每个子句中有三个文字。

• 创建一个新的“子集一致性”问题，其中包含一组整数和一个目标值，具体步骤如下：

a. 对于3SAT方程中的每个变量，创建一个值为1的数字。

b. 对于3SAT方程中的每个子句，创建一个值为2的数字。

c. 将目标值设置为变量的总数加上子句的总数。

• 如果3SAT方程可满足，那么在“子集一致性”问题中存在一个子集，通过选择满足的子句为每个变量选择一个数字，从而实现目标值的总和。

• 如果3SAT方程不可满足，那么在“子集一致性”问题中不存在一个子集，使得子集的总和等于目标值，因为任何有效的子集都需要包含至少一个值为2的整数，对应于一个满足的子句。

• 由于已知3SAT问题是NP完全的，这种规约证明了“子集一致性”是NP完全问题。

示例

#include <iostream>
#include <vector>
using namespace std;

bool ThreeSAT_Satisfiable(const vector<vector<int>>& clauses) {
   return false;
}

class SubsetUniformity {
private:
   vector<int> numbers;
   int targetValue;

public:
   SubsetUniformity(const vector<int>& vars, const vector<int>& clauses) {
      for (int v : vars) {
         numbers.push_back(1);
      }
      for (int c : clauses) {
         numbers.push_back(2);
      }
      targetValue = vars.size() + clauses.size();
   }

   bool isSubsetSumPossible(int idx, int sum) {
      if (sum == targetValue) {
         return true;
      }
      if (idx >= numbers.size() || sum > targetValue) {
         return false;
      }
      return isSubsetSumPossible(idx + 1, sum) || isSubsetSumPossible(idx + 1, sum + numbers[idx]);
   }

   bool hasSolution() {
      return isSubsetSumPossible(0, 0);
   }
};

int main() {
   vector<vector<int>> clauses = {
      {1, 2, -3},
      {-1, -2, 3},
      {-1, 2, 3}
   };

   bool isSatisfiable = ThreeSAT_Satisfiable(clauses);
   SubsetUniformity su(clauses[0], clauses[1]);

   cout << "3SAT Formula is " << (isSatisfiable ? "satisfiable." : "not satisfiable.") << endl;
   cout << "Subset Uniformity has " << (su.hasSolution() ? "a" : "no") << " solution." << endl;

   return 0;
}

输出

3SAT Formula is not satisfiable.
Subset Uniformity has a solution.

结论

这些方法论都表明，“子集权益”或者“子集集合”问题是NP近似的，因此，找到一种能够解决所有实例的有效算法是不可能的。科学家们经常使用动态规划或其他估计方法来成功解决这个问题的实际情况。