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