Минимальные деревья Штейнера и NP-полнота

В чем разница между следующими деревьями Штейнера: (не) метрическим минимальным деревом Штейнера, евклидовым минимальным деревом Штейнера, графовым минимальным деревом Штейнера и т. д.? Какие из них NP-полные, а какие NP-сложные? Некоторые из найденных мной онлайн-ресурсов предполагают, что деревья Штейнера являются NP-сложными, а другие предполагают, что они NP-полные, но я полагаю, что они имеют в виду разные версии/варианты проблемы.

Обновление: неважно, я разобрался. Проблема решения SMT является NP-полной, потому что по дереву Штейнера и целому числу k легко за полиномиальное время проверить, меньше ли стоимость дерева или равна k. Но задача оптимизации SMT не имеет полиномиального верификатора времени (мы все еще можем найти стоимость дерева, но мы не можем проверить, что это оптимальное решение), поэтому она NP-трудна.


np-hard complexity-theory np-complete
person yha    schedule 06.05.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Меня очень смущала NP-полнота и NP-трудность задач, тем более что иногда кажется, что они взаимозаменяемы.

Уловка очень проста. NP-complete — это подкласс NP, который является классом полиномиальных задач, проверяемых на решение. Таким образом, только задачи принятия решений могут быть NP-полными, а задача оптимизации никогда не бывает NP-полной.

NP-Hard означает любую задачу, которая не менее сложна, чем NP-complete, включая как решения, так и задачи оптимизации. Следовательно, все NP-полные задачи решения также являются NP-трудными. Если проблема принятия решения является NP-полной, версия оптимизации является NP-сложной, потому что, если у вас есть решение для оптимизации, вы также можете использовать его для ответа на проблему принятия решения. Однако обратное не обязательно верно.

Таким образом, технически согласно определению, даже если бы проблема оптимизации имела полиномиальный верификатор времени, она все равно не была бы NP-полной.

person Thomas Bosman    schedule 08.05.2014