time-complexity - 如何知道问题是否属于 conp？

几天前我有一个测试，并不能通过它。

有一个问题我没有正确回答，也没有看懂：

会有一个项目列表。假设我们有两个玩家（第一个和第二个）。

会有项目意义的价值函数：

项目组的值也定义为。

让我们看看两个玩家的彩信问题。我们的目标是在两个玩家之间划分所有物品（即，将他们分成两个外来的组，其单位是所有物品）。

我们将计算所有可能的分区 1,2,3 ... 等等。给定所有可能的划分中的第 i 个划分，我们用的较小子群的值来表示。这意味着：。我们将设置一个最小-最大值（最大最小尺寸）为。

例如：有 4 个项目。它们的价值：. 可能的划分是：

子组之间的排列并不重要，所以这些都是可能的划分。最大最小值为 7，并从除法 {2,5} , {3,4} 中获得。

在决策版本 MMS(E, v, z) 中，给定项目、价值函数和非负数 z，我们被问到 - 最大最小值是否等于 z？

问题1：确定该语言属于哪个等价部门：

问题 2：谁将成为见证人或算法？

有一个多项式算法在所有玩家之间贪婪地划分项目
可以构造非归属验证算法。我们的见证将被分成两个小组。验证算法将检查是否. 如果是这样，则表明给我们的 -z 不是最小值-最大值，因为存在最小值大于 -z 的除法。
假设我们的见证是分成两个子组的。如果z小于最大最小值，我们可以找出来。但是在 z 大于最大最小值的情况下，作为除法的见证对我们没有帮助。也就是说，在这个见证中，我们只能根据需要对部分输入进行反驳，而不是对所有输入进行反驳。

我不明白这两个问题。我无法在考试中回答他们。

标签： time-complexitycomplexity-theorynpcomputability