Вопрос по algorithm – Связь между NP-трудными и неразрешимыми проблемами

13

Я немного запутался в связи между неразрешимыми проблемами и трудными проблемами NP. Являются ли трудные проблемы NP подмножеством неразрешимых проблем, или они просто одинаковы и равны, или они несопоставимы?

Для меня я спорил со своими друзьями, что неразрешимые проблемы - это надстройка над трудными проблемами NP. Там будут некоторые проблемы, которые не в NP hard, но неразрешимы. Но я нахожу этот аргумент слабым и немного запутался. Есть ли NP-полные проблемы, которые неразрешимы? есть ли проблема в NP hard, которая разрешима?

Некоторое обсуждение было бы очень полезно! Спасибо!

Ваш Ответ

3   ответа
4

at least так же сложно, как любая NP-полная проблема.

Поэтому неразрешимая проблема может быть NP-трудной. Задача является NP-трудной, если оракул для нее сделает решение NP-полных задач легким (то есть решаемым за полиномиальное время). Мы можем представить себе неразрешимую проблему, такую, что при наличии оракула проблемы, полные NP, будут легко решаться. Например, очевидноevery Оракул, который решает проблему остановки, также может решить проблему NP-полной задачи, поэтому каждая задача, полная по Тьюрингу, также NP-трудна в том смысле, что (быстрый) оракул для нее сделает решение задач с NP-завершением быстрым.

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

Error: User Rate Limit Exceeded
0

например Проблема остановки Тьюринга только для NP-Hard.

                   <---------NP Hard------>
|------------|-------------||-------------|------------|--------> Computational Difficulty

|<----P--->|

|<----------NP---------->|

|<-----------Exponential----------->|

|<---------------R (Finite Time)---------------->|

На этой диаграмме эта маленькая труба показывает перекрытие NP и NP-Hard и которая показывает NP-полноту, то есть набор тех проблем, которые являются NP, а также NP-Hard.

Неразрешимыми проблемами являются NP Трудные проблемы, которые не имеют решения и которых нет в NP.

9

сколько (конечного) времени вы отдаете вашему алгоритму, он всегда будет ошибочным при вводе.

NP-hard ~ = супер-полиномиальное время работы (при условии P! = NP). Это волнообразно, но в основном NP-hard означает, что это по меньшей мере так же сложно, как самая трудная проблема в NP.

Конечно, есть проблемы с NP-сложностью, которые не являются неразрешимыми (= разрешимы). Любая NP-полная проблема будет одной из них, скажем SAT.

Есть неразрешимые проблемы, которые не являются NP-сложными? Я так не думаю, но это не легко исключить - я не вижу очевидного аргумента, что должно быть сокращение от SAT до всех возможных неразрешимых проблем. Могут быть странные неразрешимые проблемы, которые не очень полезны. Но стандартные неразрешимые проблемы (скажем, проблема остановки) являются NP-трудными.

Error: User Rate Limit Exceeded akaHuman
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded akaHuman
Error: User Rate Limit Exceeded

Похожие вопросы