Если у вас есть 4-лентная детерминированная c TM, которая принимает L в polytime, тогда L находится в P. Причина в том, что вы можете смоделировать 4-лентную TM, используя одноленточную TM, увеличив время выполнения на максимум полиномиальный фактор. Произведение многочленов есть многочлен, и у вас есть свой ответ. Доказательство этого может быть утомительным, если вы призваны сделать это, например, в контексте экзамена; но это определенно не сложно показать, что это так.
Более простое доказательство может не полагаться на 4-лентные ТМ, а напрямую записать ТМ с одной лентой для этой проблемы. Тогда никаких доказательств не требуется (за исключением того, что ваша ТМ работает, конечно). Стратегия может быть такой:
- убедитесь, что лента ввода начинается с ^ nb ^ n
- , убедитесь, что лента ввода заканчивается на b ^ nc ^ n
- halt-accept, если оба истинны, отклонить в противном случае
Если мы можем выполнить шаги 1 и 2 каждый за полиномиальное время, то общая проблема в P. Обратите внимание, что эти проблемы очень похожи; давайте рассмотрим, как мы решим первый:
- убедитесь, что мы начинаем с (так как n> = 1)
- , меняем a на A и затем сканируем, пока не найдем первый б; если b больше нет, остановите-отклоните
- , измените b на B и go назад, пока мы не найдем последнее движение A
- вправо; затем
- если другой a, повторите с шага 2
- , если B, отсканируйте вправо и убедитесь, что b больше нет; если есть, остановите-отклоните, в противном случае остановите-примите
Этот TM перемещается вперед и назад через половину строки, вычеркивая пары a и b по ходу дела. Он делает это ровно столько раз, сколько существует экземпляров a в худшем случае (когда строка является ^ nb ^ n). Поскольку (n / 2) * (n / 2) = n ^ 2/4, среда выполнения является полиномиальной.