Проблема называется «NP-hard», если есть многократное сокращение времени от каждой проблемы NP к ней.
Проблема остановки действительно NP-hard, по следующей причине:
Пусть L - проблема NP, так как L находится в NP, она разрешима - таким образом, существует детерминированная машина Тьюринга, которая решает L, обозначим ее как M. Теперь мы можем создать M ', который моделирует M иостанавливается, если M принимает x (где x - вход).И результат сокращения на входе x равен (M ', x).
Обозначим сокращение как R, и действительно, x находится в L, если R (x) находится в H.
(M (x) = 1 => M '(x) halts => (M ', x) находится в H.
M (x) = 0 => M' (x) не останавливается => (M ', x) не находится в H)
Почемуредукционный полином?Размер описания M может быть очень большим, но он ИСПРАВЛЕН.Таким образом, для создания M 'требуется постоянное время (можно посмотреть, как M' "жестко закодирован" в R), поэтому сокращение является линейным и полиномиальным.
Из-за транзитивности сокращения (т.е.если есть (полиномиальное / вычислительное) сокращение с L1 до L2 и с L2 до L3 (ДОЛЖНО БЫТЬ ТАКОЙ ЖЕ ТИП СОКРАЩЕНИЯ!), то есть сокращение с L1 до L3) достаточно показать уменьшение по сравнению с известной NP-трудной проблемойк новой проблеме, чтобы доказать, что новая проблема NP-трудна, и это обычный способ сделать это.В этом примере было удобно доказать непосредственно из определения.
Что касается вашего другого вопроса, ответ - нет.существует неразрешимая проблема, которая не является NP-трудной.Вы можете увидеть доказательство здесь: https://math.stackexchange.com/questions/642726/are-all-undecidable-problems-np-hard
Обратите внимание, что если P = NP, каждая задача (за исключением тривиальных множеств) является NP-трудной.поэтому доказательство предполагает P! = NP.