Уменьшает ли P или NP экземпляр до NP-Complete этот экземпляр также NP-Hard?

Question

Уменьшает ли P или NP экземпляр до NP-Complete этот экземпляр также NP-Hard?

Если Задача X, лежащая в P или NP, может быть уменьшена до NP-Complete, является ли эта проблема X автоматически проблемой NP-Hard?

0

complexity-theory analysis np np-complete np-hard

Источник

user2804705 25 май '18 в 14:10

1 ответ

Решение

Другие вопросы по тегам complexity-theory analysis np np-complete np-hard

user1328439 26 май '18 в 09:22 2018-05-26 09:22 · Accepted Answer · 2018-05-26 09:22

Быстрый ответ: нет, это не так.

Напомним определение NP-сложных задач.

Задача X является NP-трудной, если каждая проблема в NP может быть полиномиально сведена к X.

Если, с другой стороны, проблема X может быть полиномиально сведена к некоторой NP-полной задаче Y, это означает, что Y, по крайней мере, так же труден, как X, а не наоборот.

Наконец, если NP-полная задача Z может быть полиномиально сведена к X, то действительно X является NP-трудной, поскольку каждая проблема W в NP может быть сведена к Z, и, комбинируя два сокращения, мы можем уменьшить W до X, поэтому определение доволен.

В: Если Задача X, лежащая в P или NP, может быть уменьшена до NP-Complete, является ли эта проблема X автоматически проблемой NP-Hard?

A: нет

В: Если проблема X, лежащая в P или NP, такова, что проблема NP-Complete может быть сведена к ней, является ли эта проблема X автоматически проблемой NP-Hard?

A: да