computer-science - 如何判断一种语言是否属于 NP？

Question

例如，我知道语言

CFL 的泵引理不是上下文无关的，但我如何证明它属于 NP 而不是 exp。时间、可判定的语言还是可识别的图灵？

编辑：做了一些挖掘，我做的一个疏忽是 NP 中的问题是那些可以通过非确定性图灵机在多项式时间内验证的问题。我怎么知道：a：在多项式时间内存在该语言的验证器，并且 b：NDTM 可以识别它

Answer 1

但我如何证明它属于 NP 而不是 exp。时间、可判定的语言还是可识别的图灵？

你不能，因为那不可能发生。NP 中的每种语言都在 EXPTIME 中，是可判定的，并且是图灵可识别的。L 在 NP 中当且仅当存在多项式 p 和 PTIME 语言 L' 使得

x 在 L 中当且仅当存在长度为 p(|x|) 的 y 使得 (x,y) 在 L' 中

为了证明 NP 是 EXPTIME 的一个子集，观察一个人可以对所有可能的 y 进行蛮力搜索。并且每种 EXPTIME 语言显然都是可判定和可识别的。

现在，至于您关于显示语言 L 属于 NP 的问题：尝试想出一种方法，对于 L 中的每个 x，您可以写下它属于 L 的“证明”或“证明”。这样的对于不在 L 中的 x，证书不应该存在，并且该证书的正确性应该是可有效验证的（在多项式时间内）。证书的长度本身最多应该是 x 长度的多项式。

当然，具体如何做到这一点取决于特定的语言 L。许多 NP 问题被表述为搜索（存在）问题：这个图是否有哈密顿循环，这个布尔公式是否有一个令人满意的分配，等等。在这种情况下，证书的选择通常是明确的，可以将证书作为正在搜索的东西（哈密顿路径或令人满意的分配本身）。需要检查给定图和所谓的哈密顿路径，可以检查它是否实际上是多项式时间内的哈密顿路径，或者给定公式和所谓的令人满意的分配，可以检查它是否实际上是多项式中的令人满意的分配时间。这通常很容易显示。

请注意，P 是 NP 的子集（只需为证书获取任何内容，证书检查器可以在多项式时间内自行解决原始问题）。您要求的语言，{a^nb^nc^n | n >= 0} 在 P 中很容易（因此在 NP 中）。