Некоторые выводы о NP

Question

это мой первый вопрос на этом сайте.

Я недавно изучал NP. У меня есть путаница в этой теме, и я хочу предложить мой вывод, а кто-то проверяет меня.

I) каждая проблема NP может быть решена в Экспоненциальном времени.

II) если P = NP, то NP = NP-Complete.

III) Проблема факторизации в 2-простой коэффициент, NP.

IV), если проблема X может свести к известной проблеме NP-Hard, тогда X должен быть NP-HARD.

каждый может проверить мой вывод и узнать меня?

Answer 1

I) каждая задача NP может быть решена в экспоненциальное время.

Да, это потому, что оно может быть разрешено в полиномиальное время на Non Determinisitc Machine (определение NP) и, таким образом, может быть разрешено на детерминированной машине в экспоненциальном времени.

II) если P = NP, то NP = NP-Complete.

Да, потому что если P = NP, ответы «да» и «нет» для всех проблем NP аналогично легко достижимы, запустите алгоритм полиномиального времени для проблемы «да» и ответьте так. Результат всегда правильный и выполняется в полиномиальное время, предполагая, что такая машина полиномиального времени существует.

III) Проблема факторизации в 2-простой коэффициент, NP.

Да. Учитывая число и его первичную факторизацию - легко проверить, является ли это правильным ответом (это эквивалентное определение проблемы в NP).

IV), если проблема X может привести к известной проблеме NP-Hard, тогда X должен быть NP-HARD.

Нет, это должно быть наоборот. Вам нужно уменьшить известную проблему NP-Hard до X, а затем вы можете пометить X как NP-Hard.
Помните, что каждая проблема в NP имеет сокращение до SAT (Cook Levin theorem), и все же P! = NP-Complete (или, как мы думаем, по крайней мере)