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