私は削減について多くのことを研究しましたが、それには悪い問題があります：私はこれをCLRSから取っています：
「...問題Aの解決を問題Bの解決に「減らす」ことにより、Bの「容易さ」を使用してAの「容易さ」を証明します。」
そして、私はこれを「クリストスH.パパディミトリオウによる計算の複雑さ」から取っています。
「...問題Aは、BがAに減少した場合、少なくとも問題Bと同じくらい困難です。」
私はこれらの2つの概念と混同しました：簡単さを使用すると、問題Xは問題Yに還元され、Yの多項式時間アルゴリズムがあり、還元プロセスが多項式時間で行われる場合、問題Xは多項式時間で解くことができ、XはYより簡単か、少なくともYより難しくはありません。
しかし、硬さを使用すると、問題Xは問題Yに還元され、YはXよりも簡単であるか、少なくともXよりも難しくはありません。
私は本当に混乱しました、助けてください。特別な感謝。
最初の引用が「AをBに減らす」と言い、2番目の引用が「BをAに減らす」と言っていることを見逃したかもしれません。
XがYに減少する場合、つまりYを使用してXを解くことができる場合、XはYよりも難しくありません。これは、多項式の複雑さの減少が「無料」と見なされるためです。したがって、XをYに減少させることにより、解く方法を見つけました。 XはYに対して存在するあらゆる解を使用します。
したがって、最初の引用では、AがBに還元され、Bが簡単である場合、それはAが簡単であることを意味します（厳密に言えば、それは難しくありません）。
2番目の引用は、論理的な対偶を使用します。BがAに減少し、Bが硬い場合、Aは硬くなければなりません（厳密に言えば、それは簡単ではありません）。証明：Aが簡単だった場合、Bは簡単になります（上記のように、AとBは逆になります）。Bは簡単ではないので、Aは簡単ではありません。
「問題Xは問題Yに還元され、YはXよりも簡単であるか、少なくともXよりも難しくはない」というあなたの発言は誤りです。Yは実際にはXよりも難しい場合でも、XをYに減らすことができます（つまり、Yを使用してXを解くことができます）。したがって、NP困難な問題の特殊なケースに加算（X）を減らすことができます。 （Y）、解が2つの入力数の合計であるNP困難問題のインスタンスを多項式時間で構築するスキームを定義することによって。加算がNP困難であることを意味するのではなく、自分たちで物事を不必要に困難にしただけです。加算を実行するためのより良い方法があるため、加算を実行するためにその削減を使用することは賢明ではありません。ええと、P！= NPと仮定すると、つまり。
削減は、問題自体を削減するのではなく、特定のクラスにある問題の証拠を削減することと考えてください。この関係は、複雑さよりも論理に関連しています。
理論はこれだけです。
問題Aを解くためのアルゴリズムがあり、多項式時間で解くことができます。
問題Bを問題Aで解決できる表記法に変換し、その結果を問題Bの表記法に多項式時間で変換し直すことができる場合、問題Bも多項式時間で解決できます-合計時間としてこれは、2つの多項式を加算するだけです。したがって、難しくはありません。