computer-science - 证明语言在 NP/EXPTIME/Turing 决策者/turing 可识别（cs 理论）

Question

通过练习测试为我的 cs 理论考试做准备。在问题中，我需要说明一种语言属于哪个“区域”（RL/DFSA/NFSA）/（CFG/CFL/NPDA）/（NP）/（EXPTIME）/（DL/DTM/NDTM）/（ TR），我意识到我不确定如何证明一种语言会超过（CFG/CFL/NPDA）区域。这里有 2 个问题（3 和 5），我知道它们不能在那个区域，因为它们会导致上下文无关语言的泵引理失败，我如何确定它们会属于哪个区域？

---

编辑：答案是 3 和 5 都属于 NP，但为什么呢？

Answer 1

您说您可以证明 3 和 5 不在 NPDA 区域中。从那里接。你继续下一个，NP。在这里，您将使用各种受限的图灵机。

我可以用对数空间在线性时间内识别语言 3。数一个符号。计算 b 符号。计算 c 个符号。比较计数。这是对数据的线性扫描加上二进制数的比较（小于输入长度的线性时间）。线性时间是 NP 的一个子集。您的教授对您的要求有多详细（即您是否需要明确引入第三个字母符号来分隔您的计数？您是否需要说明如何比较二进制数？）？

要解决 5，您需要知道二进制乘法的界限。数a，数b，数c。将 a 的计数乘以 b 的计数。将结果与 c 的计数进行比较。这是对输入的线性扫描，加上二进制乘法的复杂性（但请记住，您要相乘的数字是 log(n) 位）。由于您的区域不是很严格，至少可以说我们受多项式时间的约束。因为 P 是 NP 的一个子集，所以我们在那里。

比这更高，我希望你会得到更多关于问题的冗长描述。我假设 PSPACE 在您的 EXPTIME 区域中，并且想到的典型示例是量化的布尔公式。它有点像 SAT（库克定理证明 SAT 是 NP-Hard），但有量词。有一个很好的证据表明 QBF 是 PSPACE 完备的，这与库克定理非常相似。我猜你的上下文敏感语言显然不属于另一个区域的子集也属于这里（如果你得到语言的生产规则描述）。

下一个区域是停止的图灵机。如果你能描述一个算法，无论多么荒谬（它一定是荒谬的，否则它会被之前的区域捕捉到），它可以在这里停止。

下一个区域是关于赖斯定理的。维基那个坏男孩。用赖斯定理再次证明所有的证明都很容易。这个区域比为第一个区域提出正则表达式或 FSA 更容易。