为什么国际象棋、西洋跳棋、围棋等在EXP里，却被猜想在NP里？
Why is chess, checkers, Go, etc. in EXP but conjectured to be in NP?
如果我告诉你一局棋的走法并宣布谁赢，如果真的赢了，为什么不能在多项式时间内检查呢？根据我的理解，这将使它成为一个 NP 问题。
首先：32个棋子在8x8的场地上可以摆的位置是有限的。我们需要考虑将任何棋子转换为任何其他棋子，并包括任何此类可用位置。当然，在这一切之中，也有一些棋局是按照棋规走不到的，但这无所谓。重要的是：我们有一个限制。让我们将此限制简单命名为 MaxPositions。
现在对于任何给定的位置，让我们按如下方式构建一棵树：
- 给定的位置是根。
- 添加任何位置（合法的国际象棋位置或不）作为 child。
- 对于这些 children 中的任何一个，再次将任何位置添加为 child。
- 以这种方式继续，直到您的树达到 MaxPositions 的深度。
我现在太累了，无法考虑我们是否需要为这个想法增加一层深度（证明？），但是见鬼，让我们添加它。重要的是：这样构建的树是limited.
下一步：在这棵树中，删除任何无法通过合法棋步从根部到达的 sub-tree。对剩余的children，grand-children，...重复此步骤，直到整棵树中没有剩余不可到达的位置。步数必须有限，因为树是有限的。
现在进行 breadth-first 搜索，如果之前已找到任何节点，则将其设为叶节点。它必须被标记为（！；抽取候选人？）。任何配合位置都一样。
如何判断是否有强配？在任何子树中，如果轮到您，则必须有至少 一个 child 导致强制交配。如果是对手的着法，则必须有 child for every child 导致配对。当然，这递归地适用。然而，由于树是有限的，所以整个算法是有限的。
[感应]，整个算法有限！ 一些常量限制了整个东西。所以：尽管这个限制非常高（并且远远超出了 up-to-date 硬件可以处理的范围），但它是一个限制（请不要让我计算它......）。所以：我们的问题实际上是 O(1)!!!
西洋跳棋也一样，走吧，...
到目前为止，这适用于强制配合。什么是最好的举动？首先，检查我们是否可以找到一个强迫伴侣。如果是这样，很好，我们找到了最好的一步。如果有多个，select 需要的步数最少的那个（仍然可能不止一个...）。
如果没有这样的逼偶，那么我们就需要通过某种手段来测量'best'一个。可能计算可供交配的可用继承数。其他测量建议？只要从上到下对这棵树进行操作，我们仍然是有限的。所以，我们又是 O(1).
现在我们错过了什么？再次查看您评论中的 link。他们在谈论 NxN 跳棋！作者是大小不等的字段！
所以回顾一下我们是如何构建这棵树的。我认为很明显树会随着田地的大小呈指数增长（尝试自己证明...）。
我很清楚这个答案不是证明因为问题是 EXP(TIME)。事实上，我承认，这根本不是一个真正的答案。但我认为我所说明的内容仍然很好地 image/impression 说明了问题的复杂性。而且只要没有人提供更好的答案，我敢说这总比没有好...
附录，考虑您的评论：
允许我参考wikipedia。实际上，应该足以在指数时间内转换另一个问题，而不是link中的多项式，因为应用转换+ 解决由此产生的问题仍然是指数级的。但是我不确定确切的定义...
对于您已经知道它是 EXP 完全的问题，证明这一点就足够了（将任何其他问题转换为这个问题，然后再次转换为国际象棋问题仍然是指数的，如果两个转换都是指数的）。
显然，J.M。 Robson 找到了一种方法来为 NxN 跳棋执行此操作。 generalized chess 也必须是可能的，可能只是修改 Robsons 算法。我不认为经典的 8x8 国际象棋是可能的，但是...
O(1) 仅适用于经典国际象棋，不适用于广义国际象棋。但它是我们假设不在 NP 中的后一个！实际上，在我对本附录的回答中，缺少一个证明：有限树的大小（如果 N 是固定的）不会随着 N 的增长而呈指数增长（因此答案实际上是不完整的！）。
而要证明广义国际象棋不在 NP 中，我们必须证明在 non-deterministic 图灵机上没有多项式算法可以解决该问题。这个我又打开了，我的回答更不完整...
If I tell you the moves for a game of chess and declare who wins, why
can't it be checked in polynomial time if the winner does really win?
This would make it an NP problem from my understanding.
因为为了检查赢家（白人）是否真的赢了，您还必须评估输家（黑人）在其他人中可能做出的所有可能的动作也能赢。这使得检查也呈指数增长。
如果我告诉你一局棋的走法并宣布谁赢，如果真的赢了，为什么不能在多项式时间内检查呢？根据我的理解，这将使它成为一个 NP 问题。
首先：32个棋子在8x8的场地上可以摆的位置是有限的。我们需要考虑将任何棋子转换为任何其他棋子，并包括任何此类可用位置。当然，在这一切之中，也有一些棋局是按照棋规走不到的，但这无所谓。重要的是：我们有一个限制。让我们将此限制简单命名为 MaxPositions。
现在对于任何给定的位置，让我们按如下方式构建一棵树：
- 给定的位置是根。
- 添加任何位置（合法的国际象棋位置或不）作为 child。
- 对于这些 children 中的任何一个，再次将任何位置添加为 child。
- 以这种方式继续，直到您的树达到 MaxPositions 的深度。
我现在太累了，无法考虑我们是否需要为这个想法增加一层深度（证明？），但是见鬼，让我们添加它。重要的是：这样构建的树是limited.
下一步：在这棵树中，删除任何无法通过合法棋步从根部到达的 sub-tree。对剩余的children，grand-children，...重复此步骤，直到整棵树中没有剩余不可到达的位置。步数必须有限，因为树是有限的。
现在进行 breadth-first 搜索，如果之前已找到任何节点，则将其设为叶节点。它必须被标记为（！；抽取候选人？）。任何配合位置都一样。
如何判断是否有强配？在任何子树中，如果轮到您，则必须有至少 一个 child 导致强制交配。如果是对手的着法，则必须有 child for every child 导致配对。当然，这递归地适用。然而，由于树是有限的，所以整个算法是有限的。
[感应]，整个算法有限！ 一些常量限制了整个东西。所以：尽管这个限制非常高（并且远远超出了 up-to-date 硬件可以处理的范围），但它是一个限制（请不要让我计算它......）。所以：我们的问题实际上是 O(1)!!!
西洋跳棋也一样，走吧，...
到目前为止，这适用于强制配合。什么是最好的举动？首先，检查我们是否可以找到一个强迫伴侣。如果是这样，很好，我们找到了最好的一步。如果有多个，select 需要的步数最少的那个（仍然可能不止一个...）。
如果没有这样的逼偶，那么我们就需要通过某种手段来测量'best'一个。可能计算可供交配的可用继承数。其他测量建议？只要从上到下对这棵树进行操作，我们仍然是有限的。所以，我们又是 O(1).
现在我们错过了什么？再次查看您评论中的 link。他们在谈论 NxN 跳棋！作者是大小不等的字段！
所以回顾一下我们是如何构建这棵树的。我认为很明显树会随着田地的大小呈指数增长（尝试自己证明...）。
我很清楚这个答案不是证明因为问题是 EXP(TIME)。事实上，我承认，这根本不是一个真正的答案。但我认为我所说明的内容仍然很好地 image/impression 说明了问题的复杂性。而且只要没有人提供更好的答案，我敢说这总比没有好...
附录，考虑您的评论：
允许我参考wikipedia。实际上，应该足以在指数时间内转换另一个问题，而不是link中的多项式，因为应用转换+ 解决由此产生的问题仍然是指数级的。但是我不确定确切的定义...
对于您已经知道它是 EXP 完全的问题，证明这一点就足够了（将任何其他问题转换为这个问题，然后再次转换为国际象棋问题仍然是指数的，如果两个转换都是指数的）。
显然，J.M。 Robson 找到了一种方法来为 NxN 跳棋执行此操作。 generalized chess 也必须是可能的，可能只是修改 Robsons 算法。我不认为经典的 8x8 国际象棋是可能的，但是...
O(1) 仅适用于经典国际象棋，不适用于广义国际象棋。但它是我们假设不在 NP 中的后一个！实际上，在我对本附录的回答中，缺少一个证明：有限树的大小（如果 N 是固定的）不会随着 N 的增长而呈指数增长（因此答案实际上是不完整的！）。
而要证明广义国际象棋不在 NP 中，我们必须证明在 non-deterministic 图灵机上没有多项式算法可以解决该问题。这个我又打开了，我的回答更不完整...
If I tell you the moves for a game of chess and declare who wins, why can't it be checked in polynomial time if the winner does really win? This would make it an NP problem from my understanding.
因为为了检查赢家（白人）是否真的赢了，您还必须评估输家（黑人）在其他人中可能做出的所有可能的动作也能赢。这使得检查也呈指数增长。