समय और स्थान जटिलता वर्ग

जटिलता वर्ग निर्णय समस्याओं को उस समय या स्मृति के आधार पर समूहित करते हैं जिसकी मशीन को उन्हें हल करने के लिए आवश्यकता होती है, जो गणना को लघुगणकीय स्थान से लेकर घातीय समय तक एक संरचित परिदृश्य में व्यवस्थित करता है।

Definition

एक जटिलता वर्ग उन समस्याओं का समूह है जिन्हें किसी संसाधन पर एक निश्चित सीमा के भीतर हल किया जा सकता है, आमतौर पर एक ट्यूरिंग मशीन द्वारा इनपुट लंबाई के एक फलन के रूप में उपयोग किया जाने वाला समय या कार्यशील स्मृति, प्रत्येक संसाधन के लिए नियतात्मक और गैर-नियतात्मक प्रकारों के साथ।

Scope

यह विषय नियतात्मक और गैर-नियतात्मक समय और स्थान वर्गों जैसे P, NP, L, NL, PSPACE, और EXPTIME की परिभाषा, उन्हें अलग करने वाले पदानुक्रम प्रमेय, उनके बीच समावेशन और ज्ञात संबंध, सैविच का प्रमेय जो गैर-नियतात्मक और नियतात्मक स्थान को संबंधित करता है, और प्रत्येक वर्ग की विशेषता बताने वाली पूर्ण समस्याओं को शामिल करता है।

Core questions

• समस्याओं को उनके समाधान के लिए आवश्यक समय और स्मृति के आधार पर कैसे समूहित किया जाता है?
• मानक जटिलता वर्गों के बीच कौन से समावेशन को कड़ाई से ज्ञात किया जाता है?
• गैर-नियतात्मक स्थान नियतात्मक स्थान से कैसे संबंधित है?
• किसी वर्ग की विशेषता बताने में पूर्ण समस्याओं की क्या भूमिका होती है?

Key theories

पदानुक्रम प्रमेय

असीमित रूप से अधिक समय या स्थान के साथ एक मशीन कड़ाई से अधिक भाषाओं का निर्णय कर सकती है, इसलिए समय और स्थान वर्ग उचित पदानुक्रम बनाते हैं और समस्याओं को खोए बिना संसाधनों को बर्बाद नहीं किया जा सकता है।

सैविच का प्रमेय

गैर-नियतात्मक स्थान में हल की जा सकने वाली किसी भी समस्या को उस स्थान के केवल वर्ग का उपयोग करके नियतात्मक रूप से हल किया जा सकता है, इसलिए स्मृति के लिए, समय के विपरीत, गैर-नियतात्मकता अधिकतम मामूली लाभ प्रदान करती है।

Clinical relevance

किसी समस्या को जटिलता वर्ग में रखने से चिकित्सकों को यह जानने में मदद मिलती है कि क्या उम्मीद करनी है: P में समस्याएं बड़े इनपुट तक बढ़ती हैं, PSPACE-पूर्ण समस्याएं जैसे कई खेल और नियोजन कार्य कुशल समाधान का विरोध करते हैं, और वर्ग संरचना यह मार्गदर्शन करती है कि सटीक एल्गोरिदम, अनुमान, या समस्या को फिर से डिजाइन करना है या नहीं।

History

हार्टमैनिस और स्टर्न्स ने 1965 में समय-बाधित वर्गों को परिभाषित किया और समय पदानुक्रम प्रमेय को सिद्ध किया, जिससे इस क्षेत्र की स्थापना हुई। स्थान जटिलता का विकास समानांतर में हुआ, जिसमें सैविच का 1970 का प्रमेय और बाद के परिणाम जैसे इमर्मन और स्ज़ेलेप्सेंयी द्वारा पूरक के तहत गैर-नियतात्मक स्थान का समापन शामिल है, जिसने तस्वीर को परिष्कृत किया।

Key figures

• Juris Hartmanis
• Richard Stearns
• Walter Savitch
• Stephen Cook

Seminal works

• hartmanisStearns1965
• savitch1970

Frequently asked questions

समय और स्थान जटिलता में क्या अंतर है?

समय जटिलता एक एल्गोरिथम द्वारा लिए गए चरणों की संख्या की गणना करती है, जबकि स्थान जटिलता इसके द्वारा उपयोग की जाने वाली कार्यशील स्मृति को मापती है। वे अलग तरह से व्यवहार करते हैं: गणना आगे बढ़ने पर स्थान का पुन: उपयोग किया जा सकता है, यही कारण है कि गैर-नियतात्मक स्थान नियतात्मक स्थान के सापेक्ष बहुत कम शक्तिशाली है जितना कि समय के लिए समान तुलना प्रतीत होती है।

पदानुक्रम प्रमेय क्यों मायने रखते हैं?

वे यह साबित करते हैं कि अधिक संसाधन वास्तव में अधिक समस्याओं को हल करने की अनुमति देते हैं, इस संभावना को खारिज करते हुए कि सभी वर्ग एक में ढह जाते हैं। यह गारंटी देता है, उदाहरण के लिए, कि घातीय समय में हल की जा सकने वाली समस्याएं हैं लेकिन बहुपद समय में नहीं, जो जटिलता वर्गों के पूरे ढांचे को आधार प्रदान करती हैं।