I mentioned NP hardness before.
Now that we've talked about reduction, we can revisit that definition and say--
a problem X is NP hard if we can reduce some other NP hard problem to it,
what that really means is we can use a solution to problem X to solve some NP hard problem,
that means that solving X has to be at least as hard as the NP hard problem
making it therefore NP hard.
Now, there's something sort of irritatingly circular or turtles all the way downish about this.
We want to show that some problems in NP hard we got some problem,
we have to show that we can reduce some other NP hard problem to it.
We need that problem to be NP hard. How do we show that that problem is NP hard.
Well, we can just show that there're some other NP hard problems that we could reduce to it
and so on and so on and so on, and it doesn't really seem like we could ever get anywhere this way.
But the good news is that back in 1971, Stephen Cook gave essentially the original NP hard problem
and that is SAT, so SAT we know is NP hard.
And the way that he showed that is really ingenious, he actually showed that if you had
something that could solve SAT, you could use it to simulate in polynomial time,
essentially an NP computer--right.
A computer that makes these non-deterministic choices, and since that's the case,
anything that we could run on an NP computer, we can turn into a SAT problem
and therefore, SAT is as hard as anything in NP, so that's great.
Cook got us off the ground here by giving an NP hard problem.
Now we have something else to target.
We have some other way if we want to start that some problems are NP hard.
We can just reduce SAT to it and then we're done, but at this point now,
there's actually a huge number of problems that are known to be NP hard.
If you encounter a new problem, it may already be known to be NP hard or it may very well be
that some know NP hard problem can be reduced to it,
so you don't necessarily have to go all the way to SAT to do it.
मैं NP कठोरता से पहले उल्लेख किया।
अब है कि हम कम करने के बारे में बात की है, हम उस परिभाषा और कहते हैं-- फिर से कर सकते हैं
एक समस्या X NP अगर हम यह करने के लिए कुछ अन्य NP कठिन समस्या को कम कर सकते हैं कठिन है,
जो कि वास्तव में इसका मतलब है हम कुछ NP कठिन समस्या को हल करने के लिए X समस्या का एक समाधान का उपयोग कर सकते है,
इसका मतलब है कि एक्स को सुलझाने में कम से कम NP कठिन समस्या के रूप में कड़ी के रूप में हो गया है कि
यह इसलिए NP मुश्किल बना।
अब, वहाँ है कुछ की तरह irritatingly परिपत्र या कछुए सभी तरह इस बारे में downish.
हम है कि NP मुश्किल में कुछ समस्याएं हम कुछ समस्या को दिखाने के लिए चाहते हैं,
हम कि हम यह करने के लिए कुछ अन्य NP कठिन समस्या को कम कर सकते हैं दिखाने के लिए है।
हम NP कठिन हो करने के लिए कि समस्या की जरूरत है। कैसे हम दिखाएँ कि उस समस्या एनपी मुश्किल है।
ठीक है, हम बस दिखा सकते हैं कि हम यह करने के लिए कम हो सकता है कुछ अन्य NP कठिन समस्याओं कर रहे हैं
और इतने पर और इतने पर और इतने पर, और हम कभी भी कहीं भी इस तरह से मिल सकता है जैसे यह सच में नहीं लगता है।
लेकिन वापस 1971 में, स्टीफन कुक अनिवार्य रूप से मूल NP कठिन समस्या दिया कि अच्छी खबर है
और जो बैठ गया है, तो हम जानते हैं कि SAT NP मुश्किल है।
और जिस तरह से कि वह पता चला कि वास्तव में सरल है, वह वास्तव में कि यदि आप था दिखाया
कुछ है कि SAT ठीक हो सकता है, आप इसे बहुपद समय में अनुकरण करने के लिए उपयोग कर सकते,
अनिवार्य रूप से एक NP कंप्यूटर - सही।
इन गैर नियतात्मक पसंद करता है जो किसी कंप्यूटर और है कि मामला है, के बाद से
कुछ भी है कि हम एक NP कंप्यूटर पर चला सकता है, हम एक SAT समस्या में बदल सकते हैं
और इसलिए, SAT के रूप में कुछ भी में NP, इतना महान है कि मुश्किल है।
कुक हमें एक NP कठिन समस्या देकर जमीन से यहाँ मिल गया।
अब हम कुछ और करने के लिए लक्षित है।
अगर हम कि कुछ समस्याओं NP कड़ी मेहनत कर रहे हैं शुरू करने के लिए चाहते हम कुछ अन्य तरीका है।
हम सिर्फ यह करने के लिए SAT कम कर सकते हैं और फिर हम, लेकिन इस पर अब इंगित कर रहे हैं,
वहाँ वास्तव में NP कठिन हो करने के लिए ज्ञात समस्याओं की एक बड़ी संख्या है।
यदि आप एक नई समस्या मुठभेड़, यह पहले से ही NP कठिन हो करने के लिए जाना जाता हो सकती या यह बहुत अच्छी तरह से किया जा सकता
कि कुछ पता NP कठिन समस्या यह करने के लिए कम किया जा सकता है,
तो तुम जरूरी सभी तरह SAT करने के लिए यह करने के लिए नहीं जाना है।
NP困難について前にお話ししましたが
ここから還元についてお話しします
また定義の話に戻りますが
なんらかのNP困難問題から問題Xへ
還元することができれば問題XはNP困難問題です
問題Xの答えをNP困難問題を解くために
使うことができるのです
Xの解き方は少なくともNP困難問題と
同じぐらい難しい必要があります
それゆえNP困難なのです
下にいくつかの丸がありますね
NP困難であると示すには
どうすればよいでしょうか
他のNP困難問題にまとめます
この問題もNP困難だと示したいので
同じく隣の問題にまとめます
これを繰り返します
現実的な方法には思えないかもしれませんね
しかし1971年スティーブン・クックが
NP困難問題の基本概念を提示しました
それがSATです SATはNP困難として知られています
クックが示した方法は見事なものです
SATを解けるものは
多項式時間でシミュレートするために使えます
NPコンピュータは非決定性の選択で このケース以来
NPコンピュータで実行できるものは
すべてSAT問題に変更できます
それゆえSATはNPのどれよりも難しいのです
クックは私たちにNP困難問題を与えてくれましたが
今や私たちは他もターゲットとしています
NP困難の問題に取り組む時
私たちは他の方法で取り組みます
私たちはSATの取り込みは完了しました
しかし現在では
NP困難として見なされる多くの問題が存在します
新しい問題に直面した場合でも
すでにNP困難として知られているものでしょう
NP困難問題はまとめることができます
そのためSATの方法を試す必要はありません