矛盾によって硬度がどのように低下​​するか？

Question

私は計算複雑なコースを受講する学生ではなく、そのテーマに興味があります。私は、このセクションに出くわした：

と仮定我々が証明してきた問題は、 を解決することは困難である必要があり、私たちは似た新しい問題を抱えています。私たちはそれが解決するのが難しいと思われるかもしれません。 我々は矛盾によって議論する：新しい問題が解決しやすい であると仮定する。次に、古い 問題のすべてのインスタンスを新しい問題 のインスタンスに変換して解決することによって簡単に解決できることを示すことができれば、矛盾が生じます。この は、新しい問題も難しいと定めています。

出典：Wikipedia

私はこれが何を意味するかのまわりで私の頭を包むように見えることはできません。あなたはこのプロセスを俗人の言葉で（可能な限り）説明することができますか？矛盾による証明がどのように機能するのでしょうか？

たちは古い問題は難しいです知っているが、我々は古いが新しいと少なくとも同じくらい簡単であることを意味し、新たな問題と解決にそれを減らすことができるしている矛盾ですか？この全体的なアイデアは私には混乱しています。誰かがそれを私に説明することができますか、計算の複雑さの理論の固体の背景を持っていない？

Answer 1

たちは、タスクAは大変な作業であるという事実を知っていると言います。さて、私たちはタスクBを与えられ、それが難しいかどうかを判断するよう求めました。私たちは、タスクAをいくつかの部分に効率的に分解する方法を考え、各部分はタスクBになります。つまり、タスクAは、少数のタスクBを実行することによって簡単に実行できます。今、タスクBは簡単にできますか？それがあれば、簡単にタスクAをやることができます。しかし、私はタスクAが難しいことを知っているので、それは矛盾です。したがって、タスクBも難しくなければなりません。

それは、タスクAのすべてのケースが、これは保持するためにBに削減しなければならないことに注意することが重要です。ちょうどいくつかのケースがある場合、Bは容易であり得るが、一般的にAに簡単な解決策を提供しないので、必ずしも矛盾ではない。また、AからBを減らすのに多くの時間がかかる場合（つまり、還元自体が難しい場合）、Bが簡単な場合は必ずしも矛盾ではありません。