Рассмотрим следующую проблему: с учетом решающей буквы M и строки x определите, принимает ли M x. Поскольку M является решающим фактором, мы всегда можем просто запустить M на x, чтобы получить наш ответ. Временная сложность этого полностью зависит от того, какой язык M решает и как он его решает.
Теперь для задачи (M, x) создайте новую проблему следующим образом. Пусть M 'будет новым TM: M' остановит-принимает всякий раз, когда M останавливает-принимает, и M 'входит в бесконечное число l oop всякий раз, когда M останавливает-отклоняет. Наша новая проблема заключается в следующем: учитывая (M ', x), останавливается ли M' на x?
Экземпляр первой проблемы можно преобразовать за полиномиальное время в экземпляр второй проблемы; и решение второй проблемы может быть преобразовано за полиномиальное время обратно в экземпляр первой проблемы. Это означает, что первая проблема за полиномиальное время сводится ко второй. Действительно, если бы у нас была ТМ, которая решила проблему остановки, мы могли бы использовать эту конструкцию для решения любой проблемы членства с полиномиальными издержками.
Теперь, проблема остановки за полиномиальное время сводится к проблеме принятия решения, является ли произвольный решатель М принимает некоторую строку х? Очевидно нет. Мы могли бы выбрать M как TM, который принимает строки четной длины. Тогда временная сложность решения: «М принимает х?» будет линейным по размеру задачи. Если бы проблема остановки была сводима к этому за полиномиальное время, то проблема остановки была бы в P - явно не так.