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

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

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

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

14
задан svick 8 May 2012 в 07:33
поделиться