子集和判定问题——如何在多项式时间内验证"false"的情况？
Subset sum decision problem -- how to verify "false" case in polynomial time?
我在理解如何验证是否在多项式时间内没有解决子集和问题的给定实例时遇到一些麻烦。
当然，您可以轻松验证正例：只需提供加起来等于目标总和的整数列表，并检查它们是否都在原始集合中。 (O(N))
如何在多项式时间内验证答案“false”是否正确？
实际上并不知道如何做到这一点 - 实际上推测这是不可能的！
class NP 包含可以在多项式时间内验证“是”实例的问题。子集和问题是 NP 问题的典型示例。重要的是，请注意 NP 的定义没有说明如果答案为“否”会发生什么 - 也许很容易证明这一点，或者可能没有有效的算法来这样做。
NP 的对应物是 class co-NP，它包含可以在多项式时间内验证“无”实例的问题。这种问题的一个典型例子是重言式问题——给定一个命题逻辑公式，无论给定变量的值是多少，它是否总是正确的？如果公式不是重言式，那么很容易验证这一点，方法是让某人告诉您如何将值分配给变量，以使公式为假。但是，如果公式始终为真，则不清楚如何有效地显示它。
正如P=NP问题还没有解决一样，NP=co-NP问题也悬而未决。我们不知道“是”答案快速验证的问题与“否”答案快速验证的问题是否相同。
我们所知道的是，如果任何 NP 完全问题属于 co-NP，则 NP = co-NP。由于子集和是 NP 完全的，因此没有已知的多项式时间算法来验证子集和实例的答案是否为“否”。
我在理解如何验证是否在多项式时间内没有解决子集和问题的给定实例时遇到一些麻烦。
当然，您可以轻松验证正例：只需提供加起来等于目标总和的整数列表，并检查它们是否都在原始集合中。 (O(N))
如何在多项式时间内验证答案“false”是否正确？
实际上并不知道如何做到这一点 - 实际上推测这是不可能的！
class NP 包含可以在多项式时间内验证“是”实例的问题。子集和问题是 NP 问题的典型示例。重要的是，请注意 NP 的定义没有说明如果答案为“否”会发生什么 - 也许很容易证明这一点，或者可能没有有效的算法来这样做。
NP 的对应物是 class co-NP，它包含可以在多项式时间内验证“无”实例的问题。这种问题的一个典型例子是重言式问题——给定一个命题逻辑公式，无论给定变量的值是多少，它是否总是正确的？如果公式不是重言式，那么很容易验证这一点，方法是让某人告诉您如何将值分配给变量，以使公式为假。但是，如果公式始终为真，则不清楚如何有效地显示它。
正如P=NP问题还没有解决一样，NP=co-NP问题也悬而未决。我们不知道“是”答案快速验证的问题与“否”答案快速验证的问题是否相同。
我们所知道的是，如果任何 NP 完全问题属于 co-NP，则 NP = co-NP。由于子集和是 NP 完全的，因此没有已知的多项式时间算法来验证子集和实例的答案是否为“否”。