“嵌套迷宫”问题的复杂性/可判定性？

Question

在this令人费解的SE帖子中，有一个内部无限嵌套的迷宫。受此启发，考虑以下图形问题：

设置：

1. 图

   G

   ，具有顶点

   V

   和无向边

   E

2. 还有附加有向边集

   F

   。
3. 起始顶点

   S

4. 目标顶点

   Z

我们可以使用上面的符号来定义嵌套迷宫问题，即你必须找到一条从状态

(S, 0)

到状态

(Z, 0)

的路径，使用来自

E

和

F

的边，如下所示：

1. (u, v)

   中的边

   E

   可让您进行状态转换：

   (u, n) -> (v, n)

   或

   (v, n) -> (u, n)

   对于任何

   n >= 0

   。这对应于迷宫中的普通运动。

2. (u, v)

   中的边

   F

   可让您进行状态转换：

   (u, n) -> (v, n + 1)

   或

   (v, n + 1) -> (u, n)

   对于任何

   n >= 0

   。这对应于进入/退出嵌套迷宫，状态的第二个元素跟踪“深度”。

路径是一系列边（允许重复！）。

有没有一个通用的算法可以解决这个问题？似乎它是不可判定的，但是上面令人困惑的帖子中的特定示例并不是特别难分析。

编辑：再想一想，你可以通过合并 G 中所有可相互到达的顶点来丢弃 E 吗？那么，问题只是 V 和 F 上的一个，你想要找到一条路径（可能涉及重复的边），使用向前或向后的边，向前遍历的次数等于向后遍历的次数。此外，前向遍历的次数必须至少是路径所有前缀的后向遍历的次数。

Answer 1

可能有点矫枉过正，但考虑到还没有答案，这里有一个方法来表明这个问题是可以解决的。

给定这个问题的一个实例，您可以很容易地定义一个下推自动机，它定义一个非空语言，前提是该实例有一个解决方案。操作方法如下：

• 状态：添加了一种附加状态的图的顶点：

  V U {v_reject}

  。
• 输入字母：有序对的集合

  {(u, v, d): u, v in V, d in {-1, 0, 1}}

  。
• 堆栈字母表：单例集

  {1}

• 过渡：
  • 对于

    (u, v)

    中的每个

    E

    ，在读取

    u

    的输入时添加从

    v

    到

    (u, v, 0)

    的转换，对于

    (v, u, 0)

    的输入反之亦然。两次转换都应该保持堆栈不变。
  • 对于

    (u, v)

    中的每个

    F

    ，在读取

    u

    的输入时添加从

    v

    到

    (u, v, 1)

    的转换。此转换应将

    1

    推入堆栈。
  • 对于

    (u, v)

    中的每个

    F

    ，在读取

    v

    的输入时添加从

    u

    到

    (u, v, -1)

    的转换，这会从堆栈中弹出

    1

    ，但前提是堆栈非空.
  • 对于上述三种情况处理之外的任何输入，请转换到

    v_reject

    。
• 初始/最终状态：

  S

  和

  Z

原始实例的任何解决方案都定义了该 PDA 接受的输入，反之亦然。在原始问题中，状态由一个顶点和一个自然数组成。在 PDA 公式中，状态只是一个顶点，状态元组的第二个元素通过堆栈的大小来跟踪。

因为 CFG 空性是可判定的，所以这个问题也是可判定的。