अभिकलनात्मक जटिलता सिद्धांत
अभिकलनात्मक जटिलता सिद्धांत समस्याओं को हल करने के लिए किसी भी एल्गोरिथम को आवश्यक समय, स्मृति और अन्य संसाधनों की मात्रा के आधार पर वर्गीकृत करता है, जो कुशलता से हल करने योग्य है और जो दुर्गम प्रतीत होता है, उसके बीच स्पष्ट रेखाएँ खींचता है।
Definition
अभिकलनात्मक जटिलता सिद्धांत अभिकलनात्मक समस्याओं की आंतरिक कठिनाई का अध्ययन करता है, जिसे ट्यूरिंग मशीन जैसे मॉडल पर उन्हें हल करने के लिए आवश्यक संसाधनों, मुख्य रूप से चलने वाले समय और स्मृति द्वारा मापा जाता है, और तदनुसार समस्याओं को जटिलता वर्गों में समूहित करता है।
Scope
यह क्षेत्र समय और स्थान जटिलता वर्गों जैसे P, NP, PSPACE, और बहुपद पदानुक्रम, NP-पूर्णता और बहुपद-समय कटौती का सिद्धांत, केंद्रीय P बनाम NP प्रश्न, और यादृच्छिकता, अंतःक्रिया और प्रमाणों को शामिल करने वाले संसाधन-सीमित मॉडल, साथ ही इन वर्गों से संबंधित पदानुक्रम और कठोरता परिणामों को शामिल करता है।
Sub-topics
Core questions
- किसी दिए गए समस्या को हल करने के लिए स्वाभाविक रूप से कितना समय और स्मृति की आवश्यकता होती है?
- कौन सी समस्याएं कुशलता से हल की जा सकती हैं और कौन सी सभी कुशल एल्गोरिदम का विरोध करती प्रतीत होती हैं?
- समस्याओं को जटिलता वर्ग के सबसे कठिन सदस्यों जितना कठिन कैसे दिखाया जाता है?
- क्या यादृच्छिकता, अंतःक्रिया या गैर-निर्धारण वास्तविक कम्प्यूटेशनल शक्ति जोड़ते हैं?
Key theories
- समय और स्थान पदानुक्रम प्रमेय
- सख्ती से अधिक समय या स्थान दिए जाने पर, मशीनें सख्ती से अधिक समस्याओं को हल कर सकती हैं, यह साबित करते हुए कि जटिलता वर्ग वास्तविक पदानुक्रम बनाते हैं और कुछ समस्याएं दूसरों की तुलना में स्वाभाविक रूप से कठिन होती हैं।
- NP-पूर्णता
- कुक-लेविन प्रमेय NP में उन समस्याओं की पहचान करता है जिन पर हर दूसरी NP समस्या कम हो जाती है, इसलिए उनमें से किसी एक के लिए एक कुशल एल्गोरिथम उन सभी को कुशलता से हल कर देगा।
- संसाधन-सीमित मॉडल
- यादृच्छिकता, अंतःक्रिया या प्रत्यावर्तन जोड़ने से BPP, IP और बहुपद पदानुक्रम जैसे वर्ग परिभाषित होते हैं, जिनके संबंध यह स्पष्ट करते हैं कि अतिरिक्त संसाधन क्या खरीद सकते हैं और क्या नहीं।
Clinical relevance
जटिलता सिद्धांत यह प्रमाणित करके अभ्यास का मार्गदर्शन करता है कि कौन सी समस्याएं कुशल एल्गोरिदम को स्वीकार करती हैं और कौन सी NP-कठिन हैं और इसलिए अनुमानों या सन्निकटन के साथ सबसे अच्छी तरह से हमला किया जाता है; कुछ समस्याओं की अनुमानित कठोरता आधुनिक क्रिप्टोग्राफी को भी रेखांकित करती है, जिसकी सुरक्षा कम्प्यूटेशनल रूप से अव्यवहार्य माने जाने वाले कार्यों पर निर्भर करती है।
History
हार्टमैनिस और स्टर्न्स ने 1965 में जटिलता वर्गों को परिभाषित करके और पदानुक्रम प्रमेय को साबित करके इस क्षेत्र की स्थापना की। कुक और लेविन ने 1971 के आसपास NP-पूर्णता की शुरुआत की, कार्प ने 1972 में कई प्राकृतिक समस्याओं को पूर्ण दिखाया, और अगले दशकों में यादृच्छिक, इंटरैक्टिव और संभाव्य रूप से जांच योग्य प्रमाण मॉडल जोड़े गए।
Key figures
- Stephen Cook
- Richard Karp
- Leonid Levin
- Juris Hartmanis
Related topics
Seminal works
- cook1971
- hartmanisStearns1965
- aroraBarak2009
Frequently asked questions
- अभिकलनीयता और जटिलता में क्या अंतर है?
- अभिकलनीयता यह पूछती है कि क्या कोई समस्या किसी भी एल्गोरिथम द्वारा हल की जा सकती है, लागत की उपेक्षा करते हुए। जटिलता मानती है कि समस्या हल करने योग्य है और पूछती है कि उस समाधान को समय और स्मृति में कितना महंगा होना चाहिए, उन समस्याओं के बीच बेहतर अंतर खींचना जो सिद्धांत रूप में हल करने योग्य हैं।
- व्यवहार में NP-पूर्णता क्यों मायने रखती है?
- जब कोई समस्या NP-पूर्ण दिखाई जाती है, तो यह हजारों अन्य समस्याओं से जुड़ी होती है जिनके लिए दशकों के प्रयास के बावजूद कोई कुशल एल्गोरिथम ज्ञात नहीं है। यह संकेत देता है कि एक तेज़ सटीक एल्गोरिथम की तलाश शायद व्यर्थ है और सन्निकटन, अनुमान या विशेष-मामले के तरीके यथार्थवादी मार्ग हैं।