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

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

NP-hard - это проблема, которая, по крайней мере, такая же сложная, как любая NP-полная проблема.

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

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

Answer 3

Неразрешимая проблема, например, проблема остановки Тьюринга - только NP-Hard.

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

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

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

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

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

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

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