这个有限的图形问题可以决定吗？哪些因素使问题可以决定？

Question

我想知道以下问题是否可以决定以及如何找出答案。我看到的每个问题我都可以说“是”或“否”，因此除了少数（提供的）外，大多数问题和算法都可以决定 这里)?

输入：指导和有限的图$ g $，带有$ V $和$ u $作为顶点
问题：$ g $中的路径是否为$ u $作为初始顶点和$ v $作为最终顶点？

Answer 1

任何需要仅检查有限数据的问题都是可决定的，因为有一种算法包括列举所有潜在的解决方案。它可能很慢，但这并不相关：如果有算法，则可以决定。

您陈述的问题假设有限图，这强烈暗示它是可决定的。严格来说，您需要进一步看。问题是图中路径上的属性，当图包含一个周期时，有时会有无限数量的路径（您可以根据自己的喜好绕过此周期循环多次。但是，很容易将问题转换为有限问题：如果有任何路径以$ u $开头，并以$ v $结尾，其中包括一个周期，那么您可以在该路径中删除所有周期，并且您有一个不包括周期的新解决方案。由于有有限数量的路径不涉及周期（如果该图具有$ k $边缘，则最多有$ k！$路径不会使用相同的边缘多次使用），因此找到一个问题的问题从$ u $到$ v $的路径是限制的，因此可以决定。

顺便说一下，该属性称为 连接性.

这种方法是一种常见的方法 减少. 。考虑到一个不直接的问题，我们将其简化为我们知道如何解决的问题。

通常很难证明问题是不可决定的。为了证明问题是可决定的，我们需要做的就是展示一种决定这一点的算法。为了证明问题是不可决定的，我们需要证明不存在算法。有一些众所周知的不可决定的问题。实际上，在大多数情况下，当我们证明问题是不可确定的时，我们表明存在一个众所周知的不可决定的问题，可以减少我们的问题。由于我们问题的算法将解决众所周知的不可确定的问题，因此我们的问题也必须是不可决定的。

您不能真正说“大多数”问题是可决定的，或者“大多数”问题是不可决定的。从某些理论意义上讲，几乎所有问题都是无法确定的，但是我们有很大的倾向来解决“有趣的”问题，而这些问题更有可能有解决方案。

Answer 2

正如吉尔斯（Gilles）在评论中指出的那样，这个问题是微不足道的。至于你的另一个问题...

除少数（提供）外，大多数问题和算法可决定 这里)?

没有。实际上， 最多 问题是不确定的。实际上，有很多问题（语言），但是只有许多图灵机器人可以计数，这意味着最多可以计算许多可决定的问题。

Answer 3

是的，这是可以决定的，因为您可以详尽地搜索所有可能的路径。无需查看重复顶点的任何路径，因为可以跳过“弯路”。但是，任何非重复路径的长度都受图形的大小为有限的界限，因此只有有限的许多这样的路径，可以一一检查。

无法确定的内容如下：给定无限图$ g $和两个顶点$ a $和$ b $，请确定是否有从$ a $到$ b $的途径。如果将图作为甲骨文给出，并且如果图形通过计算它的程序给出，则这是无法决定的。

Answer 4

没有方法可以告诉您特定问题是否可决定。随着时间的流逝，您可能会得到一个良好的“直觉”，无论是否可以决定一个特定问题。

我通常要做的是以下内容：

1. 尝试解决问题。也就是说，尝试考虑解决给定问题的计算机程序。对于您建议的问题 - 一个非常简单的程序只会检查任何可能的路径，因此将始终成功找到它（如果存在），或者告诉您没有其他路径。
2. 清楚地提出问题。许多问题太模糊了，但是当清楚地写出时，很容易看出是否可以决定（通过与其他问题（已知是无/可决定的），或者使用已知的方法（例如 赖斯的定理)
3. 如果（2）不起作用，但您仍然认为问题是不可决定的，请尝试通过减少不确定的问题（停止问题（或其补充）在许多情况下起作用）来证明这一点。

几乎总是，当尝试做出不可确定的问题的步骤（1）时，您将需要您的程序检查 无穷 事物数量。这通常表明问题不是可决定的。