「NP困難」の版間の差分

'''NP困難''' (（-こんなん、NP-hard)hard）とは[[計算複雑性理論]]における問題のクラスの1つ。直観的に言えば「[[NP]]に属する最も難しい問題と比べて、少なくとも同等以上に難しい」問題である。問題 ''H'' がNP困難のクラスに属するとは、「[[NP完全問題]]に属する何れかの問題 ''L'' が ''H'' へ[[チューリング還元]]可能である」と定義される。即ち<math>\scriptstyle L\, \leq\,_T H</math>であり、NP困難問題を解ける[[神託機械]]がもしあれば、それを利用してNP完全問題を多項式時間で解くことができる。<br>

* NP完全問題同士は互いに多項式時間帰着可能なので、すべてのNP完全問題は ''H'' に還元して多項式時間で解ける。従ってNPに属する全ての問題も ''H'' に還元できる。但ただしここでは二種類の変換を組み合わせていることに注意されたい。NP完全に属する決定問題をNP完全な問題 ''L'' に帰着する際は多項式時間変換であり、''L'' を ''H'' に変換する際はチューリング還元である。