如何判断一种语言是否属于NP？
例如，我知道语言 
CFL 的泵引理不是上下文无关的，但我如何证明它属于 NP 而不是实验值。时间，可判定的语言，还是图灵可识别的？
编辑：做了一些挖掘，我犯的一个疏忽是，NP 中的问题是那些可以通过非确定性图灵机在多项式时间内验证的问题。我怎么知道： a：该语言在多项式时间内存在一个验证器 b：NDTM 可以识别它
for example, I know that the language
isnt context free by the pumping lemma for CFLs, but how would i prove that it falls into NP and not exp. time, decidable languages, or turing recognizable?
EDIT: Did some digging, and one oversight i made is that problems in NP are those that a verifiable in polynomial time BY a Nondeterministic Turing Machine. How would I know:
a: There is a verifier that exists for this language in polynomial time
and b: a NDTM can recognize it
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你不能，因为那不可能发生。 NP 中的每种语言都在 EXPTIME 中，是可判定的，并且是图灵可识别的。 L 属于 NP 当且仅当存在多项式 p 和 PTIME 语言 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 中）。
You cannot, because that cannot happen. Every language in NP is in EXPTIME, is decidable, and is Turing recognizable. L is in NP if and only if there is a polynomial p and a PTIME language L' such that
To show that NP is a subset of EXPTIME, observe that one can just do a brute-force search for all possible y. And every EXPTIME langauge is obviously decidable and recognizable.
Now, as for your question about showing a language L belongs to NP : Try to come up with a way by which for each x in L, you can write down a "proof" or "certificate" that it belongs to L. Such a certificate should not exist for x not in L, and that this certificate is correct should be efficiently verifiable (in polynomial time). The length of the certificate should itself be at most polynomial in the length of x.
Exactly how one does this depends on the particular language L, of course. Many NP problems are phrased as search (existence) problems : does this graph have a Hamiltonian cycle, does this boolean formula have a satisfying assignment, and so on. In this case, the choice for the certificate is usually clear, one can take the certificate to be the thing being searched for (the Hamiltonian path or satisfying assignment itself). One needs to check that given a graph and an alleged Hamiltonian path, one can check if it is actually a Hamiltonian path in polynomial time, or given a formula and an alleged satisfying assignment, one can check if it is actually a satisfying assignment in polynomial time. This is usually easy to show.
Note that P is a subset of NP (just take anything for the certificate, the certificate-checker can solve the original problem itself in polynomial time). The language you asked for, {a^n b^n c^n | n >= 0} is quite easily in P (and hence in NP).