是语言L：= {a ^ nb ^ nc ^ n | n> = 1} in P？

Question

L：= {a ^ nb ^ nc ^ n | n> = 1}不正常（无法泵送）。

但是我可以很容易地找到可以在多倍时间内接受L的4磁带确定性图灵机。

因此L应该在P中对吗？

Answer 1

[如果您有一个4带确定性TM在多项式中接受L，则L在P中。原因是，您可以通过将运行时间最多增加一个多项式来使用单带TM模拟4带TM。因子。多项式的乘积是一个多项式，您就有答案了。如果要求您这样做，证明这可能令人望而生畏。在考试范围内；但肯定不是很难证明这种情况。

更简单的证明可能不依赖于4磁带TM，而是针对此问题直接写下单磁带TM。则无需证明（当然，除了TM可以工作之外）。一个策略可能是这样的：

1. 确保输入磁带以a ^ n b ^ n开头
2. 确保输入磁带以b ^ n c ^ n结尾
3. 如果两个都成立，则暂停接受，否则拒绝

如果我们可以在多项式时间内分别执行步骤1和2，则总问题在P中。请注意，这些问题非常相似；让我们考虑一下如何解决第一个问题：

1. 确保我们以（开始，因为n> = 1）
2. 将a更改为A，然后扫描直到找到第一个b；如果没有更多b，则停止]
3. 将b更改为B，然后返回直到找到最后一个A
4. 向右移动；然后
   • [如果是另一个，请从步骤2重复
   • 如果是B，请正确扫描并确保没有更多b；如果存在，则停止拒绝，否则停止接受

此TM在字符串的一半之间来回移动，同时将a和b对交叉。在最坏的情况下（当字符串为a ^ n b ^ n时），它的执行次数与a实例的执行次数完全相同。由于（n / 2）*（n / 2）= n ^ 2/4，所以运行时是多项式。