YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Hindi subtitles

← 06-30 SAT is NP-Hard

Get Embed Code
3 Languages

Showing Revision 1 created 03/23/2013 by Nirmal Khatua.

  1. मैं NP कठोरता से पहले उल्लेख किया।
  2. अब है कि हम कम करने के बारे में बात की है, हम उस परिभाषा और कहते हैं-- फिर से कर सकते हैं
  3. एक समस्या X NP अगर हम यह करने के लिए कुछ अन्य NP कठिन समस्या को कम कर सकते हैं कठिन है,
  4. जो कि वास्तव में इसका मतलब है हम कुछ NP कठिन समस्या को हल करने के लिए X समस्या का एक समाधान का उपयोग कर सकते है,
  5. इसका मतलब है कि एक्स को सुलझाने में कम से कम NP कठिन समस्या के रूप में कड़ी के रूप में हो गया है कि
  6. यह इसलिए NP मुश्किल बना।
  7. अब, वहाँ है कुछ की तरह irritatingly परिपत्र या कछुए सभी तरह इस बारे में downish.
  8. हम है कि NP मुश्किल में कुछ समस्याएं हम कुछ समस्या को दिखाने के लिए चाहते हैं,
  9. हम कि हम यह करने के लिए कुछ अन्य NP कठिन समस्या को कम कर सकते हैं दिखाने के लिए है।
  10. हम NP कठिन हो करने के लिए कि समस्या की जरूरत है। कैसे हम दिखाएँ कि उस समस्या एनपी मुश्किल है।
  11. ठीक है, हम बस दिखा सकते हैं कि हम यह करने के लिए कम हो सकता है कुछ अन्य NP कठिन समस्याओं कर रहे हैं
  12. और इतने पर और इतने पर और इतने पर, और हम कभी भी कहीं भी इस तरह से मिल सकता है जैसे यह सच में नहीं लगता है।
  13. लेकिन वापस 1971 में, स्टीफन कुक अनिवार्य रूप से मूल NP कठिन समस्या दिया कि अच्छी खबर है
  14. और जो बैठ गया है, तो हम जानते हैं कि SAT NP मुश्किल है।
  15. और जिस तरह से कि वह पता चला कि वास्तव में सरल है, वह वास्तव में कि यदि आप था दिखाया
  16. कुछ है कि SAT ठीक हो सकता है, आप इसे बहुपद समय में अनुकरण करने के लिए उपयोग कर सकते,
  17. अनिवार्य रूप से एक NP कंप्यूटर - सही।
  18. इन गैर नियतात्मक पसंद करता है जो किसी कंप्यूटर और है कि मामला है, के बाद से
  19. कुछ भी है कि हम एक NP कंप्यूटर पर चला सकता है, हम एक SAT समस्या में बदल सकते हैं
  20. और इसलिए, SAT के रूप में कुछ भी में NP, इतना महान है कि मुश्किल है।
  21. कुक हमें एक NP कठिन समस्या देकर जमीन से यहाँ मिल गया।
  22. अब हम कुछ और करने के लिए लक्षित है।
  23. अगर हम कि कुछ समस्याओं NP कड़ी मेहनत कर रहे हैं शुरू करने के लिए चाहते हम कुछ अन्य तरीका है।
  24. हम सिर्फ यह करने के लिए SAT कम कर सकते हैं और फिर हम, लेकिन इस पर अब इंगित कर रहे हैं,
  25. वहाँ वास्तव में NP कठिन हो करने के लिए ज्ञात समस्याओं की एक बड़ी संख्या है।
  26. यदि आप एक नई समस्या मुठभेड़, यह पहले से ही NP कठिन हो करने के लिए जाना जाता हो सकती या यह बहुत अच्छी तरह से किया जा सकता
  27. कि कुछ पता NP कठिन समस्या यह करने के लिए कम किया जा सकता है,
  28. तो तुम जरूरी सभी तरह SAT करने के लिए यह करने के लिए नहीं जाना है।