1

如果我告诉你一盘棋的走法并宣布谁赢了，如果赢家真的赢了，为什么不能在多项式时间内检查呢？根据我的理解，这将使它成为一个 NP 问题。

4

2 回答 2

2

首先：您可以在 8x8 场地上设置 32 件的位置数量是有限的。我们需要考虑将任何棋子转换为任何其他棋子，并包括任何此类可用位置。当然，在这其中，也有一些位置是按照国际象棋的规则是达不到的，但这无所谓。重要的是：我们有一个限制。让我们将此限制简称为 MaxPositions。

现在对于任何给定的位置，让我们构建一棵树，如下所示：

  • 给定的位置是根。
  • 添加任何位置（合法的国际象棋位置与否）作为子级。
  • 对于这些孩子中的任何一个，再次将任何位置添加为孩子。
  • 以这种方式继续，直到您的树达到 MaxPositions 的深度。

我现在太累了，不知道我们是否需要一个额外的深度来实现这个想法（证明？），但见鬼，让我们添加它。重要的是：这样构造的树是有限的。

下一步：在这棵树中，删除任何通过合法棋步从根无法到达的子树。对剩余的孩子、孙子、...重复此步骤，直到整个树中没有无法到达的位置。步数必须是有限的，因为树是有限的。

现在进行广度优先搜索，如果之前已经找到任何节点，则将其设为叶子。它必须被标记为这样（！；抽奖候选人？）。任何配合位置都一样。

如何判断是否有强迫交配？在任何子树中，如果轮到您，则必须至少有一个孩子导致强制交配。如果是对方的招式，每一个孩子都必须有一个孙子才能引出一个配偶。当然，这递归地适用。但是，由于树是有限的，所以整个算法是有限的。

[感测]，这整个算法是有限的！有一些恒定的限制整个东西。所以：虽然限制非常高（并且远远超出了最新硬件可以处理的范围），但它是一个限制（请不要让我计算它......）。所以：我们的问题实际上是O(1)！！！

跳棋也一样，去，...

到目前为止，这适用于强制配对。最好的举动是什么？首先，检查我们是否可以找到一个强迫的伴侣。如果是这样，很好，我们找到了最好的举动。如果有多个，请选择所需移动最少的一个（仍然可能不止一个......）。

如果没有这样的强迫配偶，那么我们需要通过某种方式衡量“最佳”配偶。可能计算可供配对的继任数。其他测量建议？只要在这棵树上从上到下操作，我们仍然是有限的。再说一次，我们是O(1)。

现在我们错过了什么？再次查看您评论中的链接。他们在谈论 NxN 跳棋！作者是大小不等的领域！

因此，回顾一下我们是如何构建树的。我认为很明显，树随着字段的大小呈指数增长（尝试自己证明......）。

我很清楚这个答案并不能证明问题是 EXP(TIME)。实际上，我承认，这根本不是一个真正的答案。但我认为我说明的内容仍然很好地说明了问题的复杂性。而只要没有人提供更好的答案，我敢说这总比没有好……

附录，考虑到您的评论：

让我允许参考维基百科。实际上，在指数时间内转换另一个问题就足够了，而不是链接中的多项式，因为应用转换+解决结果问题仍然是指数的。但我不确定确切的定义......

对于您已经知道它是 EXP 完成的问题，证明这一点就足够了（如果两个转换都是指数的，则将任何其他问题转换为这个问题，然后再转换为国际象棋问题仍然是指数的）。

显然，JM Robson 为 NxN 跳棋找到了一种方法。通用国际象棋也必须是可能的，可能只是简单地修改罗布森算法。不过，我认为经典的 8x8 国际象棋是不可能的……

O(1) 仅适用于古典国际象棋，不适用于通用国际象棋。但我们假设后者不在 NP 中！实际上，在我对本附录的回答中，缺少一个证明：有限树的大小（如果 N 是固定的）不会随着 N 的增长而呈指数增长（所以答案实际上是不完整的！）。

为了证明广义国际象棋不在NP中，我们必须证明没有多项式算法可以在非确定性图灵机上解决问题。我再次打开这个，我的答案仍然不完整......

于 2016-05-29T23:54:28.030 回答
0

如果我告诉你一盘棋的走法并宣布谁赢了，如果赢家真的赢了，为什么不能在多项式时间内检查呢？根据我的理解，这将使它成为一个 NP 问题。

因为为了检查获胜者（白色）是否真的赢了，你还必须评估松散者（黑色）可能在其他人中做出的所有可能的动作也能获胜。这使得检查也是指数级的。

于 2018-11-05T16:59:09.293 回答