子集相等性是NP完全的

1. 什么是子集相等性问题

在计算机科学中，子集相等性问题是指给定两个集合，判断它们是否相等的问题。例如，对于集合 A = {1, 3, 5} 和集合 B = {5, 1, 3}，它们是相等的，因为它们包含的元素相同，只是排列顺序不同。

1.1 NP问题

子集相等性问题属于NP问题，也就是“非确定性多项式时间问题”的简称。NP问题是指能在多项式时间内验证一个解的问题。如果存在一个解，则可以在多项式时间内验证该解是否正确。

例如，对于子集相等性问题，如果两个集合相等，则可以在多项式时间内验证它们相等。因此，这个问题属于NP问题。

2. 子集相等性问题的NP完全性证明

通过证明子集相等性问题是一个NP完全问题，可以说明该问题的困难程度。在计算理论中，如果一个问题是NP完全问题，就说明它是非常困难的，很难找到解决方案。

2.1 子集相等性问题属于NP问题

首先，我们需要证明子集相等性问题属于NP问题。假设有两个集合 A 和 B，我们想要验证它们是否相等。假设存在一个证明 P，它可以证明这两个集合是相等的。

证明 P 可以是一个集合，其中包含所有的 A 中的元素。如果这些元素在 B 中都存在，并且 B 中的元素也都在 A 中出现过，我们可以得出结论：A 和 B 是相等的。

验证这个证明的复杂度是多项式级别的，因此子集相等性问题属于NP问题。

2.2 子集相等性问题是NP完全问题

为了证明子集相等性问题是NP完全问题，我们需要证明它是一个NP问题，并且可以通过一个NP完全问题进行归约得到。

首先证明它是NP问题已经在前面完成了。因此我们只需要证明它可以通过一个NP完全问题进行归约得到。

我们选择3-SAT问题作为我们要归约到的NP完全问题。3-SAT是指每个子句中有三个变量的布尔表达式的可满足性问题。它是一个已知的NP完全问题。

我们将3-SAT实例转换成一个集合。假设有一个布尔表达式，包含 n 个变量和 m 个子句。我们将这个布尔表达式转换成一个集合，其中集合元素的个数是 m+n。

对于每个子句，我们创建一个大小为 3 的子集。每个子集包含三个元素，和一个辅助元素。对于每个变量，我们创建两个大小为 2 的子集。第一个子集包含变量的两种取值，第二个子集包含变量的否定和肯定两种取值。

例如，假设原始的布尔表达式是 (x₁ ∨ ?x₂ ∨ x₃) ∧ (?x1 ∨ x3 ∨ ?x4)。我们将它转换成一个集合，其中包含以下元素：

S₁ = {x₁, ?x₂, x₃, a₁}

S₂ = {?x₁, x₃, ?x₄, a₂}

S₃ = {x₁, a₃}

S₄ = {?x₁, a₄}

S₅ = {x₂, a₅}

……

S_n+1 = {x_n, a_n+1}

其中 a₁ 到 a_n+1 是辅助元素。

我们将每个子句的子集 S_i 中的元素与相应变量的两个子集中的元素进行匹配。如果子集 S_i 中包含 x_j，则我们从第 j 个变量的第一个子集中选择一个元素，将它添加到 S_i 中。如果子集 S_i 中包含 ?x_j，则我们从第 j 个变量的第二个子集中选择一个元素，将它添加到 S_i 中。

例如，对于 S₁，我们将 x₁ 从第一个变量的第一个子集中选择，将 ?x₂ 从第二个变量的第二个子集中选择，将 x₃ 从第三个变量的第一个子集中选择。

这样，我们就将3-SAT问题转换成了一个子集相等性问题。如果原始的布尔表达式是可满足的，意味着对于每个子句中至少一个变量的取值是真的。因此，我们可以将每个子句中任意一个为真的变量添加到相应的子集中。这样我们得到了一个大小为 m 的子集的集合，它们在 n+m 个元素中的分配正好覆盖了每个大小为 3 的子集的每个元素。

反之，如果存在一个大小为 m 的子集的集合，它们在 n+m 个元素中的分配正好覆盖了每个大小为 3 的子集的每个元素。则意味着对于每个子句，至少有一个变量取值是真的。因此，原始的布尔表达式是可满足的。

这样，我们就证明了子集相等性问题可以通过一个NP完全问题进行归约得到。因此，它也是NP完全问题。

3. 总结

子集相等性问题是NP完全问题。它是一个经典的问题，计算机科学中许多其他问题都可以归约到它。这个问题的NP完全性证明表明，计算机科学中存在许多问题，它们非常困难，很难找到解决方案。在实践中，我们需要运用计算机科学知识和算法技术，才能找到解决这些问题的方法。

bool subsetEqual(int arr1[], int arr2[], int n){
    vector<int> v1, v2;
    for(int i=0; i<n; i++){
        v1.push_back(arr1[i]);
        v2.push_back(arr2[i]);
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    if(v1 == v2)
        return true;
    return false;
}