Если нижняя граница задачи экспоненциальная, значит, это NP?

Предполагая, что у нас есть задача $p$ мы показали, что нижняя граница для решения $p$ равна $\mathcal{\Omega}(2^n)$ .

может нижняя граница $\mathcal{\Omega}(2^n)$ влечет проблему в $NP$ ?

time-complexity np-complete kelalaka
источник

Это не NP, но это NP-жесткий.

user35734

Откуда ты знаешь, что это NP-хард?

Юваль Фильмус

Если бы вы могли показать проблему как в

и в NP, вы бы доказали P

NP.

Ω (2^{n})

$\mathcal{\Omega}(2^n)$

\neq

$\neq$

kasperd

@kasperd: Мы называем это Пазлами Меркля, но это должно быть исключено из P =? NP, потому что конкретная форма не дает других с такими же свойствами, и в противном случае доказательство P = NP, вероятно, исключает любой способ создания Пазлов Меркля, которые фактически работают как предназначены. Экспоненциальное время Пазлы Меркля также PSPACE для предполагаемого пользователя.

Джошуа

Загадки @Joshua Merkle не являются экспоненциальными в зависимости от длины ввода . (Хорошо, если мы предположим, что решение для Алисы является полиномиальным).

rus9384

Ответы:

$\Omega(2^n)$

$2^n$ $c^{n^\epsilon}$

NP - верхняя граница сложности задачи.

Юваль Фильмус
источник

Ω (2^{n})

$\Omega(2^n)$

Вы можете построить такую проблему, используя диагонализацию.

Юваль Фильмус

Извините, я не следую. Что диагонализируется? Перечисляем ли мы проблемы или алгоритмы? Как следует не-NP-твердость?

Марио Карнейру

2^{n}

$2^n$

Нет. Во-первых, как указывает Ювал , проблема может быть гораздо сложнее, чем нижняя граница, которую вы доказали.

$\Theta(2^n)$ $\mathbf{NP}$ $\mathbf{P}=\mathbf{NP}$ $\mathrm{TIME}[\Omega(2^n)]$ $\mathbf{NP}$ $\mathbf{P}\neq\mathbf{NP}$ $\mathbf{NP}$

$\mathbf{NP}$ $\mathbf{NP}$

Дэвид Ричерби
источник