undecidable問題とNPハード問題の関係について少し混乱しています。 NP困難な問題が決定不能な問題のサブセットであるか、それとも単に同じで均等であるか、それとも同等ではないのか？NPハードとundecidable問題の関係
私にとって、私は、決定不能な問題はNPの難しい問題のスーパーセットであると私の友人と主張してきました。 NPではなく、決めることのできない問題がいくつか存在します。しかし、私はこの議論が弱いと思っていて、ちょっと混乱しています。決めることができないNP完全な問題はありますか？決定可能なNPハードに問題はありますか？
いくつかのディスカッションは大きな助けになるでしょう！ありがとう！
いくつかの入力に対しては、不可能=不可能です。どのくらいの（有限の）時間をあなたのアルゴリズムを与えるに関係なく、それは常にいくつかの入力に間違っています。
NP-hard〜=超多項式実行時間（P！= NPとする）。それは手で波打つが、基本的にはNP難しいということは、少なくともNPで最も難しい問題ほど難しいということを意味する。
確かに決めることはできない（決定可能な）NPハードな問題があります。どんなNP完全な問題でも、SATと言ってもいいでしょう。
NP困難ではない決定不可能な問題はありますか？私はそうは考えていませんが、それを排除するのは容易ではありません - 私は、SATから決定不能なすべての問題への削減が必要であるという明らかな議論は見られません。非常に有用ではない奇妙で決定不能な問題があるかもしれません。しかし、標準的な決めることができない問題（停止問題、例えば）はNP困難です。
NP-hardは、以上で、少なくとものNP完全な問題と同じくらい難しい問題です。
したがって、決定不可能な問題はNP-hardになる可能性があります。問題はNP-hardであるため、NP-complete問題を簡単に解くことができれば多項式時間で解くことができます。私たちは、それについてのオラクルを考えると、NP完全な問題を解決するのは容易ではないという、決めることのできない問題を想像することができます。たとえば、明らかにすべてのオラクルは停止問題を解決することもNP完全な問題を解決することができますので、すべてのTuring完全な問題も、（高速）オラクルがNP完全問題は簡単です。
したがって、チューリング完全な決定不可能な問題は、NP困難な問題のサブセットです。
誰かが証拠に「明らかに」言うときはいつでも、アラーム音が鳴り始める。 – OrangeDog
解決できない問題。 Turing Halting ProblemはNP困難のみです。小さなパイプがNPとNP困難とその重複示すことがこの図で
<---------NP Hard------>
|------------|-------------||-------------|------------|--------> Computational Difficulty
|<----P--->|
|<----------NP---------->|
|<-----------Exponential----------->|
|<---------------R (Finite Time)---------------->|
は、NP完全、NPならびにNP困難であるそれらの問題、すなわちセットを示します。
解決できない問題は解決策がなく、NPにないNP困難な問題です。
さて、私は結論に達しているようです。決めることのできない問題は、NPの難しい問題のサブセットです。これは、次のシナリオに基づいています。 NPのすべての問題は決定可能です。決めることができない（=決定可能で、NP完全であると思われる）NPハードにはいくつかの問題があります。したがって、決めることのできない問題は、NPハードのサブセットで構成されます。私は正しい？ – akaHuman
あなたは私を "したがって"迷わせました。確かに封じ込めは他の方法では行かないが、2つのセットは比類のないかもしれない。決まっていない問題がNP困難であることを証明する必要があります（つまり、ポリタイムでSATを解決するためのオラクルとして使用できます）。 –
よろしくお願いします。私はほとんどそれを得るようです。 – akaHuman