证明一种语言在 NP/EXPTIME/Turing 决策器/图灵可识别中（cs 理论）
通过练习测试来准备我的计算机科学理论考试。在这个问题中，我需要说明语言属于哪个“区域”(RL/DFSA/NFSA)/(CFG/CFL/NPDA)/(NP)/(EXPTIME)/(DL/DTM/NDTM)/( TR) 我意识到我不确定如何证明一种语言可以通过（CFG/CFL/NPDA）区域。我知道这里有两个问题（3和5）不能在该区域中，因为它们将无法通过上下文无关语言的泵引理，我如何确定它们将属于哪个区域？
编辑：答案是 3 和 5 都属于 NP，但为什么呢？
prepping for my cs theory exam by running through a practice test. I nthe problem, I need to state in which "zone" a language belongs to (RL/DFSA/NFSA)/(CFG/CFL/NPDA)/(NP)/(EXPTIME)/(DL/DTM/NDTM)/(TR)
and I realized im not sure how to prove what a language would be past the (CFG/CFL/NPDA) zone. Here are 2 problems (3 and 5) that I know cannot be in that zone since they would fail the pumping lemma for context free langages, how could i determine what zone they would fall under?
EDIT: The answersare that both 3 and 5 both fall into NP, but why?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你说你可以证明3和5不在NPDA区域内。从那里接。你继续下一个，NP。从这里开始，您将使用各种受限的图灵机。
我可以在对数空间的线性时间中识别语言 3。数一下 a 符号。数一下 b 符号。数一下 c 符号。比较计数。这是对数据的线性扫描加上二进制数的比较（小于输入长度的线性时间）。线性时间是 NP 的子集。您的教授要求您详细程度如何（即您是否需要明确引入第三个字母符号来分隔您的计数？您是否需要阐明如何比较二进制数？）？
要解 5，您需要知道二进制乘法的界限。数a，数b，数c。将 a 的计数乘以 b 的计数。将结果与 c 的计数进行比较。这是对输入的线性扫描加上二进制乘法的复杂性（但请记住，您相乘的数字是 log(n) 位）。由于您的区域限制不是很严格，所以至少可以说我们受到多项式时间的约束。因为 P 是 NP 的子集，所以我们就在那里。
如果比这个更高，我希望您会得到更冗长的问题描述。我假设 PSPACE 在您的 EXPTIME 区域中，并且想到的典型示例是量化布尔公式。它有点像 SAT（库克定理证明 SAT 是 NP 难的），但带有量词。有一个很好的证明表明 QBF 是 PSPACE 完备的，这与库克定理非常相似。我猜测您的上下文敏感语言显然不属于另一个区域的子集，但也属于此处（如果您获得该语言的生产规则描述）。
下一个区域是停止的图灵机。如果你能描述一个算法，无论多么荒谬（它必须是荒谬的，否则它会被之前的区域捕获），它可以停在这里。
下一个区域是关于赖斯定理的。维基那个坏男孩。利用赖斯定理，所有证明都变得容易了。该区域比为第一个区域提供正则表达式或 FSA 更容易。
You stated that you can prove that 3 and 5 are not in the NPDA zone. Pick up from there. You move on to the next, NP. Here on out, you work with variously restricted turing machines.
I can recognize language 3 in linear time with logarithmic space. Count the a symbols. Count the b symbols. Count the c symbols. Compare the counts. That's a linear scan through the data plus a comparison of binary numbers (which is less than linear time for the input length). Linear time is a subset of NP. How detailed would your professor require you to be (i.e. do you need to explicitly introduce a third alphabet symbol to separate your counts? Do you need to spell out how to compare binary numbers?)?
To solve 5, you'll need to know the bounds of binary multiplication. Count a, count b, count c. Multiply the count of a by the count of b. Compare the result to the count of c. That's a linear scan through the input plus whatever the complexity of binary multiplication is (but remember that the numbers you are multiplying are log(n) bits). Since your zone isn't very restrictive, let's at least say we're bound by polynomial time. Since P is a subset of NP, we're there.
Any higher than this, and I'd expect that you'll get more wordy descriptions of problems. I assume that PSPACE is in your EXPTIME zone, and the canonical example that comes to mind is quantified boolean formula. It's sort of like SAT (Cook's theorem proves SAT is NP-Hard), but with quantifiers. There's a nice proof to show QBF is PSPACE complete that is quite analogous to Cook's theorem. I'm guessing that your context sensitive languages that do not obviously belong to a subset in another zone also belong here (in case you get a production rule description of the language).
The next zone is Turing machines that halt. If you can describe an algorithm, no matter how ridiculous (and it must be ridiculous, or it would have been caught by a previous zone), it can stop here.
The next zone is all about Rice's theorem. Wiki that bad boy. All proofs are easy again with Rice's theorem. This zone is easier than coming up with a regex or FSA for the first zone.