जटिलता वर्ग

File:Complexity subsets pspace.svg

कई महत्वपूर्ण जटिलता वर्गों के बीच संबंधों का प्रतिनिधित्व

कम्प्यूटेशनल जटिलता सिद्धांत में, एक जटिलता वर्ग संबंधित संसाधन-आधारित कम्प्यूटेशनल जटिलता की कम्प्यूटेशनल समस्याओं का एक समुच्चय(गणित) है। दो सबसे सामान्य रूप से विश्लेषित संसाधन समय जटिलता और स्थान जटिलता हैं।

सामान्यतः, एक जटिलता वर्ग को एक प्रकार की कम्प्यूटेशनल समस्या, गणना का एक मॉडल, और समय जटिलता या अंतरिक्ष जटिलता जैसे सीमित संसाधन के रूप में परिभाषित किया जाता है। विशेष रूप से, अधिकांश जटिलता वर्गों में निर्णय की समस्याएं होती हैं जो ट्यूरिंग मशीन के साथ हल करने योग्य होती हैं, और उनके समय या स्थान (स्मृति) आवश्यकताओं से भिन्न होती हैं। उदाहरण के लिए, वर्ग P (जटिलता) बहुपद समय में नियतात्मक ट्यूरिंग मशीन द्वारा हल की जाने वाली निर्णय समस्याओं का समूह है। चुकीं, अन्य प्रकार की समस्याओं (जैसे समस्या (जटिलता) और कार्य समस्याओं की गिनती) और गणना के अन्य मॉडलों (जैसे संभाव्य ट्यूरिंग मशीन, इंटरैक्टिव प्रूफ प्रणाली, बूलियन सर्किट और एक कंप्यूटर जितना ) का उपयोग करने के संदर्भ में परिभाषित कई जटिलता वर्ग हैं। ).

जटिलता वर्गों के बीच संबंधों का अध्ययन सैद्धांतिक कंप्यूटर विज्ञान में अनुसंधान का एक प्रमुख क्षेत्र है। जटिलता वर्गों के अधिकांशतः सामान्य पदानुक्रम होते हैं; उदाहरण के लिए, यह ज्ञात है कि कई मौलिक समय और स्थान जटिलता वर्ग निम्नलिखित विधियों से एक दूसरे से संबंधित हैं: NL (जटिलता)⊆P (जटिलता)⊆NP (जटिलता)⊆PSPACE⊆EXPTIME⊆EXPSPACE (जहां ⊆ दर्शाता है सबसम्मुचय संबंध)। चुकीं, कई रिश्ते अभी तक ज्ञात नहीं हैं; उदाहरण के लिए, कंप्यूटर विज्ञान में सबसे प्रसिद्ध खुली समस्याओं में से एक P बनाम NP से संबंधित है। कक्षाओं के बीच संबंध अधिकांशतः संगणना की मौलिक प्रकृति के बारे में सवालों के जवाब देते हैं। उदाहरण के लिए, P बनाम NP समस्या, सामान्यतः उन सवालों से संबंधित है कि क्या गैर नियतात्मक एल्गोरिथम कंप्यूटरों में कोई कम्प्यूटेशनल पावर जोड़ता है और क्या समाधान वाली समस्याएं जिन्हें जल्दी से शुद्धता के लिए जांचा जा सकता है, उन्हें भी जल्दी से हल किया जा सकता है।

पृष्ठभूमि

जटिलता वर्ग संबंधित कम्प्यूटेशनल समस्याओं के समुच्चय(गणित) हैं। उन्हें समय या स्मृति जैसे विशेष कम्प्यूटेशनल संसाधनों के संबंध में उनके अन्दर निहित समस्याओं को हल करने की कम्प्यूटेशनल कठिनाई के संदर्भ में परिभाषित किया गया है। अधिक औपचारिक रूप से, एक जटिलता वर्ग की परिभाषा में तीन चीजें होती हैं: एक प्रकार की कम्प्यूटेशनल समस्या, गणना का एक मॉडल और एक बाध्य कम्प्यूटेशनल संसाधन। विशेष रूप से, अधिकांश जटिलता वर्गों में निर्णय की समस्याएं होती हैं जिन्हें ट्यूरिंग मशीन द्वारा सीमित समय जटिलता या अंतरिक्ष जटिलता संसाधनों के साथ हल किया जा सकता है। उदाहरण के लिए, जटिलता वर्ग P (जटिलता) को निर्णय समस्याओं के समुच्चयके रूप में परिभाषित किया जाता है जिसे बहुपद समय में नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है।

कम्प्यूटेशनल समस्याएं

सहजता से, एक कम्प्यूटेशनल समस्या केवल एक प्रश्न है जिसे कलन विधि द्वारा हल किया जा सकता है। उदाहरण के लिए, प्राकृतिक संख्या है $n$ अभाज्य संख्या? एक कम्प्यूटेशनल समस्या है। एक कम्प्यूटेशनल समस्या को गणितीय रूप से समस्या के उत्तरों के समुच्चय(गणित) के रूप में दर्शाया जाता है। प्रारंभिक उदाहरण में, समस्या (इसे कॉल करें ${\texttt {PRIME}}$) सभी प्राकृत संख्याओं के समुच्चय द्वारा दर्शाया जाता है जो अभाज्य हैं: ${\texttt {PRIME}}=\{n\in \mathbb {N} |n{\text{ is prime}}\}$. अभिकलन के सिद्धांत में, इन उत्तरों को स्ट्रिंग (कंप्यूटर विज्ञान) के रूप में दर्शाया जाता है; उदाहरण के लिए, प्रारंभिक उदाहरण में प्राकृतिक संख्याओं को अंश ्स के स्ट्रिंग्स के रूप में दर्शाया जा सकता है जो बाइनरी संख्या ों का प्रतिनिधित्व करते हैं। इस कारण से, कम्प्यूटेशनल समस्याओं को अधिकांशतः पर्यायवाची रूप से भाषाओं के रूप में संदर्भित किया जाता है, क्योंकि बिट्स के तार औपचारिक भाषाओं का प्रतिनिधित्व करते हैं (भाषाविज्ञान से उधार ली गई अवधारणा); उदाहरण के लिए, यह कहना कि ${\texttt {PRIME}}$ समस्या जटिलता वर्ग में है NP(जटिलता) यह कहने के बराबर है कि भाषा ${\texttt {PRIME}}$ NP में है।

निर्णय समस्याएं

File:Decision Problem.svg

एक निर्णय समस्या में किसी भी इनपुट पर केवल दो संभावित आउटपुट हैं, हां या नहीं (वैकल्पिक रूप से, 1 या 0)।

सैद्धांतिक कंप्यूटर विज्ञान में सबसे अधिक विश्लेषित समस्याएँ निर्णय समस्याएँ हैं - ऐसी समस्याएँ जिन्हें हाँ-नहीं प्रश्नों के रूप में प्रस्तुत किया जा सकता है। उदाहरण के लिए, ऊपर दिया गया प्राथमिक उदाहरण, एक निर्णय समस्या का एक उदाहरण है क्योंकि इसे हां-नहीं प्रश्न द्वारा प्रस्तुत किया जा सकता है जो कि प्राकृतिक संख्या है $n$ अभाज्य संख्या । अभिकलन के सिद्धांत के संदर्भ में, एक निर्णय समस्या को इनपुट स्ट्रिंग्स के समुच्चयके रूप में दर्शाया जाता है, जो कि एक सही एल्गोरिथ्म चलाने वाला कंप्यूटर हां में उत्तर देगा। प्रारंभिक उदाहरण में, ${\texttt {PRIME}}$ प्राकृतिक संख्याओं का प्रतिनिधित्व करने वाले स्ट्रिंग्स का समुच्चयहै, जब एक एल्गोरिदम चलाने वाले कंप्यूटर में इनपुट किया जाता है जो सही ढंग से प्रारंभिक परीक्षण करता है, एल्गोरिदम हाँ का उत्तर देता है, यह संख्या प्रमुख है। यह हाँ-नहीं प्रारूप अधिकांशतः समान रूप से स्वीकार-अस्वीकार के रूप में कहा जाता है; अर्थात्, एक एल्गोरिद्म एक इनपुट स्ट्रिंग को स्वीकार करता है यदि निर्णय समस्या का उत्तर हाँ है और यदि उत्तर नहीं है तो उसे अस्वीकार कर देता है।

चुकीं कुछ समस्याओं को सरली से निर्णय समस्याओं के रूप में व्यक्त नहीं किया जा सकता है, फिर भी वे कम्प्यूटेशनल समस्याओं की एक विस्तृत श्रृंखला को सम्मिलित करती हैं। अन्य प्रकार की समस्याएं जिन्हें कुछ जटिलता वर्गों के रूप में परिभाषित किया गया है, उनमें फलन समस्याएं सम्मिलित हैं (जैसे एफP(जटिलता)), गिनती की समस्या (जटिलता) (जैसे शार्प-पी|#पी), अनुकूलन समस्याएं, और वादा समस्याएं (अनुभाग देखें) अन्य प्रकार की समस्याएं)।

कम्प्यूटेशनल मॉडल

कंप्यूटर की धारणा को ठोस बनाने के लिए, सैद्धांतिक कंप्यूटर विज्ञान में कम्प्यूटेशनल मॉडल के संदर्भ में समस्याओं का विश्लेषण किया जाता है। कम्प्यूटेशनल मॉडल समय और मेमोरी जैसे कम्प्यूटेशनल संसाधनों की धारणाओं को सटीक बनाते हैं। कम्प्यूटेशनल जटिलता सिद्धांत में, जटिलता वर्ग समस्याओं की अंतर्निहित संसाधन आवश्यकताओं से निपटते हैं न कि संसाधनों की आवश्यकताओं से जो भौतिक कंप्यूटर के निर्माण पर निर्भर करते हैं। उदाहरण के लिए, वास्तविक दुनिया में अलग-अलग कंप्यूटरों को एक ही समस्या को हल करने के लिए अलग-अलग मात्रा में समय और मेमोरी की आवश्यकता हो सकती है क्योंकि जिस तरह से उन्हें इंजीनियर किया गया है। कंप्यूटरों का एक अमूर्त गणितीय निरूपण प्रदान करके, कम्प्यूटेशनल मॉडल वास्तविक दुनिया की अनावश्यक जटिलताओं (जैसे प्रोसेसर (कंप्यूटिंग) गति में अंतर) को दूर करते हैं जो मूलभूत सिद्धांतों की समझ में बाधा डालते हैं।

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

एक ठोस कम्प्यूटेशनल मॉडल का उल्लेख किए बिना जटिलता वर्गों को परिभाषित करने के लिए ब्लम स्वयंसिद्धों का उपयोग करना भी संभव है, लेकिन जटिलता सिद्धांत में इस दृष्टिकोण का कम बार उपयोग किया जाता है।

नियतात्मक ट्यूरिंग मशीनें

Main article: ट्यूरिंग मशीन

File:Turing machine 2b.svg

ट्यूरिंग मशीन का एक उदाहरण। बी रिक्त प्रतीक को इंगित करता है।

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

यंत्रवत्, एक ट्यूरिंग मशीन (TM) टेप की एक असीम रूप से लंबी पट्टी पर निहित प्रतीकों (सामान्यतः बिट्स 0 और 1 को वास्तविक जीवन के कंप्यूटरों के लिए एक सहज कनेक्शन प्रदान करने के लिए प्रतिबंधित) में हेरफेर करती है। TM एक टेप हेड का उपयोग करके एक बार में पढ़ और लिख सकता है। ऑपरेशन पूरी तरह से प्राथमिक निर्देशों के एक परिमित समुच्चय द्वारा निर्धारित किया जाता है जैसे कि स्थिति 42 में, यदि देखा गया प्रतीक 0 है, तो 1 लिखें; यदि देखा गया प्रतीक 1 है, तो स्थिति 17 में बदलें; स्थिति 17 में, यदि देखा गया प्रतीक 0 है, तो 1 लिखें और स्थिति 6 में बदलें। ट्यूरिंग मशीन अपने टेप पर केवल इनपुट स्ट्रिंग से प्रारंभ होती है और हर जगह खाली होती है। TM इनपुट को स्वीकार करता है यदि यह निर्दिष्ट स्वीकृत स्थिति में प्रवेश करता है और इनपुट को अस्वीकार करता है यदि यह अस्वीकार स्थिति में प्रवेश करता है। नियतात्मक ट्यूरिंग मशीन (DTM) ट्यूरिंग मशीन का सबसे मूलभूत प्रकार है। यह अपने भविष्य के कार्यों को निर्धारित करने के लिए नियमों के एक निश्चित समुच्चय का उपयोग करता है (यही कारण है कि इसे नियतात्मक कहा जाता है)।

एक कम्प्यूटेशनल समस्या को ट्यूरिंग मशीन के संदर्भ में परिभाषित किया जा सकता है क्योंकि इनपुट स्ट्रिंग्स के समुच्चय के रूप में एक विशेष ट्यूरिंग मशीन स्वीकार करती है। उदाहरण के लिए, प्राथमिक समस्या ${\texttt {PRIME}}$ ऊपर से स्ट्रिंग्स (प्राकृतिक संख्याओं का प्रतिनिधित्व करने वाला) का समुच्चय है जो कि एक ट्यूरिंग मशीन एक एल्गोरिदम चला रही है जो सही ढंग से प्रारंभिक परीक्षण स्वीकार करती है। एक ट्यूरिंग मशीन को एक भाषा को पहचानने के लिए कहा जाता है (याद रखें कि समस्या और भाषा बहुत हद तक कम्प्यूटेबिलिटी और जटिलता सिद्धांत का पर्याय हैं) अगर यह भाषा में उपस्थित सभी इनपुट को स्वीकार करती है और कहा जाता है कि यह एक भाषा तय करती है यदि यह सभी इनपुट को अस्वीकार करती है जो नहीं हैं भाषा में (कुछ इनपुट के कारण ट्यूरिंग मशीन हमेशा के लिए चल सकती है, इसलिए पुनरावर्ती समुच्चय पुनरावर्ती गणना योग्य समुच्चय पर अतिरिक्त बाधा डालता है कि ट्यूरिंग मशीन को सभी इनपुट पर रुकना चाहिए)। एक ट्यूरिंग मशीन जो किसी समस्या को हल करती है, सामान्यतः इसका अर्थ है कि वह भाषा तय करती है।

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

गैर नियतात्मक ट्यूरिंग मशीन

Main article: गैर नियतात्मक ट्यूरिंग मशीन

Error creating thumbnail:

नियतात्मक और गैर-नियतात्मक संगणना की तुलना। यदि गैर-नियतात्मक संगणना पर कोई शाखा स्वीकार करती है तो NTM स्वीकार करता है।

नियतात्मक ट्यूरिंग मशीन (DTM) गैर-निर्धारिती ट्यूरिंग मशीन (NTM) का एक प्रकार है। सहज रूप से, एक NTM सिर्फ एक नियमित ट्यूरिंग मशीन है जिसमें किसी दिए गए स्थिति से कई संभावित भविष्य की कार्रवाइयों का पता लगाने में सक्षम होने की क्षमता है, और एक शाखा का चयन करना है जो स्वीकार करता है (यदि कोई स्वीकार करता है)। यही है, जबकि एक DTMको गणना की केवल एक शाखा का पालन करना चाहिए, एक NTMको गणना के पेड़ के रूप में कल्पना की जा सकती है, प्रत्येक चरण में कई संभावित कम्प्यूटेशनल मार्गों में शाखाएं (छवि देखें)। यदि पेड़ की कम से कम एक शाखा स्वीकृत शर्त के साथ रुकती है, तो NTM इनपुट को स्वीकार करता है। इस तरह, एक NTM को समानांतर में सभी कम्प्यूटेशनल संभावनाओं की खोज करने और एक स्वीकार करने वाली शाखा का चयन करने के बारे में सोचा जा सकता है। NTM शारीरिक रूप से वसूली योग्य मॉडल नहीं हैं, वे केवल सैद्धांतिक रूप से दिलचस्प सार मशीनें हैं जो कई दिलचस्प जटिलता वर्गों को जन्म देती हैं (जो अधिकांशतः शारीरिक रूप से वसूली योग्य समकक्ष परिभाषाएं होती हैं)।

NTMकी समय जटिलता NTMकी गणना की किसी भी शाखा पर उपयोग किए जाने वाले चरणों की अधिकतम संख्या है। इसी तरह, NTMकी अंतरिक्ष जटिलता कोशिकाओं की अधिकतम संख्या है जो NTMअपनी गणना की किसी भी शाखा पर उपयोग करती है।

DTMs को NTMs के एक विशेष स्थितियों के रूप में देखा जा सकता है जो गैर नियतात्मक की शक्ति का उपयोग नहीं करते हैं। इसलिए, DTMद्वारा की जा सकने वाली प्रत्येक गणना समकक्ष NTM द्वारा भी की जा सकती है। DTM का उपयोग करके किसी भी NTM का अनुकरण करना भी संभव है (DTM हर संभव कम्प्यूटेशनल शाखा को एक-एक करके गणना करेगा)। इसलिए, दोनों संगणनीयता के स्थितियों में समान हैं। चुकीं, DTM के साथ NTM का अनुकरण करने के लिए अधिकांशतः अधिक समय और/या स्मृति संसाधनों की आवश्यकता होती है; जैसा कि देखा जाएगा, कम्प्यूटेशनल समस्याओं के कुछ वर्गों के लिए यह मंदी कितनी महत्वपूर्ण है, कम्प्यूटेशनल जटिलता सिद्धांत में एक महत्वपूर्ण प्रश्न है।

संसाधन सीमा

जटिलता वर्ग समूह कम्प्यूटेशनल समस्याओं को उनकी संसाधन आवश्यकताओं द्वारा। ऐसा करने के लिए, कम्प्यूटेशनल समस्याओं को संसाधनों की अधिकतम मात्रा पर ऊपरी सीमा द्वारा विभेदित किया जाता है जो कि सबसे कुशल एल्गोरिदम उन्हें हल करने के लिए लेता है। अधिक विशेष रूप से, जटिलता वर्ग विशेष कम्प्यूटेशनल समस्याओं को हल करने के लिए आवश्यक संसाधनों में वृद्धि की दर से संबंधित हैं क्योंकि इनपुट आकार बढ़ता है। उदाहरण के लिए, जटिलता वर्ग 'P (जटिलता)' में समस्याओं को हल करने में लगने वाला समय बहुपद दर से बढ़ता है क्योंकि इनपुट आकार बढ़ता है, जो घातीय जटिलता वर्ग 'EXPTIME' (या) में समस्याओं की तुलना में तुलनात्मक रूप से धीमा है अधिक सटीक रूप से, 'EXPTIME' में समस्याओं के लिए जो 'P' के बाहर हैं, चूंकि ${\mathsf {P}}\subseteq {\mathsf {EXPTIME}}$).

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

समय सीमा

Main article: समय जटिलता

ट्यूरिंग मशीन मॉडल के संबंध में एक एल्गोरिथ्म की समय जटिलता एक दिए गए इनपुट आकार पर एक एल्गोरिथ्म को चलाने के लिए ट्यूरिंग मशीन के लिए आवश्यक कदमों की संख्या है। औपचारिक रूप से, ट्यूरिंग मशीन के साथ कार्यान्वित एल्गोरिदम के लिए समय जटिलता $M$ फलन के रूप में परिभाषित किया गया है $t_{M}:\mathbb {N} \to \mathbb {N}$, कहाँ $t_{M}(n)$ चरणों की अधिकतम संख्या है $M$ लंबाई के किसी भी इनपुट को लेता है .

कम्प्यूटेशनल जटिलता सिद्धांत में, सैद्धांतिक कंप्यूटर वैज्ञानिक विशेष रनटाइम मानों के साथ कम और कार्यों के सामान्य वर्ग के साथ अधिक चिंतित होते हैं जो समय जटिलता फलन में आते हैं। उदाहरण के लिए, क्या समय जटिलता एक बहुपद कार्य करती है? एक लघुगणक फलन ? एक घातीय कार्य? या किसी अन्य प्रकार का कार्य?

अंतरिक्ष सीमा

Main article: अंतरिक्ष जटिलता

ट्यूरिंग मशीन मॉडल के संबंध में एल्गोरिदम की अंतरिक्ष जटिलता ट्यूरिंग मशीन के टेप पर कोशिकाओं की संख्या है जो किसी दिए गए इनपुट आकार पर एल्गोरिदम चलाने के लिए आवश्यक होती है। औपचारिक रूप से, ट्यूरिंग मशीन के साथ प्रयुक्त किए गए एल्गोरिथम की अंतरिक्ष जटिलता $M$ फलन के रूप में परिभाषित किया गया है $s_{M}:\mathbb {N} \to \mathbb {N}$, जहाँ $s_{M}(n)$ कोशिकाओं की अधिकतम संख्या है कि $M$ लंबाई के किसी भी इनपुट पर उपयोग करता है .

मूल जटिलता वर्ग

See also: जटिलता वर्गों की सूची

मूल परिभाषाएं

जटिलता वर्गों को अधिकांशतः DTIME और NTIME (समय जटिलता के लिए) और DSPACE और NSPACE (अंतरिक्ष जटिलता के लिए) नामक जटिलता वर्गों के दानेदार समुच्चय का उपयोग करके परिभाषित किया जाता है। बिग O नोटेशन का उपयोग करते हुए, उन्हें निम्नानुसार परिभाषित किया गया है:

• समय जटिलता वर्ग ${\mathsf {DTIME}}(t(n))$ द्वारा तय की गई सभी समस्याओं का समुच्चय है $O(t(n))$ समय नियतात्मक ट्यूरिंग मशीन।
• समय जटिलता वर्ग ${\mathsf {NTIME}}(t(n))$ द्वारा तय की गई सभी समस्याओं का समुच्चय है $O(t(n))$ समय गैर नियतात्मक ट्यूरिंग मशीन।
• अंतरिक्ष जटिलता वर्ग ${\mathsf {DSPACE}}(s(n))$ द्वारा तय की गई सभी समस्याओं का समुच्चय है $O(s(n))$ अंतरिक्ष नियतात्मक ट्यूरिंग मशीन।
• अंतरिक्ष जटिलता वर्ग ${\mathsf {NSPACE}}(s(n))$ द्वारा तय की गई सभी समस्याओं का समुच्चय है $O(s(n))$ अंतरिक्ष गैर नियतात्मक ट्यूरिंग मशीन।

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

Main article: समय जटिलता

P और NP

Main articles: P (जटिलता) and NP (जटिलता)

P उन समस्याओं का वर्ग है जो बहुपद समय में नियतात्मक ट्यूरिंग मशीन द्वारा हल करने योग्य हैं और NP उन समस्याओं का वर्ग है जो बहुपद समय में एक गैर-नियतात्मक ट्यूरिंग मशीन द्वारा हल करने योग्य हैं। या अधिक औपचारिक रूप से,

${\mathsf {P}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})$

${\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k})$

P को अधिकांशतः समस्याओं का वर्ग कहा जाता है जिसे नियतात्मक कंप्यूटर द्वारा जल्दी या कुशलता से हल किया जा सकता है, क्योंकि P में किसी समस्या को हल करने की जटिलता इनपुट आकार के साथ अपेक्षाकृत धीमी गति से बढ़ती है।

वर्ग NP की एक महत्वपूर्ण विशेषता यह है कि इसे समान रूप से उन समस्याओं के वर्ग के रूप में परिभाषित किया जा सकता है जिनके समाधान बहुपद समय में नियतात्मक ट्यूरिंग मशीन द्वारा 'सत्यापन योग्य' हैं। अर्थात्, एक भाषा NP में है यदि वहाँ एक नियतात्मक बहुपद समय ट्यूरिंग मशीन उपस्थित है, जिसे सत्यापनकर्ता के रूप में संदर्भित किया जाता है, जो इनपुट के रूप में एक स्ट्रिंग लेता है $w$ और एक बहुपद आकार का प्रमाणपत्र (जटिलता) स्ट्रिंग $c$, और स्वीकार करता है $w$ अगर $w$ भाषा में है और अस्वीकार करता है $w$ अगर $w$ भाषा में नहीं है। सहजता से, प्रमाण पत्र गणितीय प्रमाण के रूप में कार्य करता है कि इनपुट $w$ भाषा में है। औपचारिक रूप से:

NP भाषाओं का वर्ग है $L$ जिसके लिए एक बहुपद-समय नियतात्मक ट्यूरिंग मशीन उपस्थित है $M$ और एक बहुपद $p$ ऐसा कि सभी के लिए $w\in \{0,1\}^{*}$, $w$ में है $L$ अगर और केवल अगर कुछ उपस्थित है $c\in \{0,1\}^{p(|w|)}$ ऐसा है कि $M(w,c)$ स्वीकार करता है।

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

Pबनाम NPसमस्या

जबकि समस्याओं के उस वर्ग के बीच एक स्पष्ट अंतर प्रतीत हो सकता है जो कुशलता से हल करने योग्य हैं और उन समस्याओं के वर्ग के बीच जिनके समाधान केवल कुशलता से जांचे जा सकते हैं, P और NP वास्तव में कंप्यूटर विज्ञान में सबसे प्रसिद्ध अनसुलझी समस्याओं में से एक के केंद्र में हैं: P बनाम NP समस्या। जबकि मालूम हो कि P$\subseteq$NP(सहज रूप से, नियतात्मक ट्यूरिंग मशीनें केवल गैर-नियतात्मक ट्यूरिंग मशीनों का एक उपवर्ग हैं जो उनके नोडेटर्मिनिज़्म का उपयोग नहीं करती हैं; या सत्यापनकर्ता परिभाषा के अंतर्गत, P उन समस्याओं का वर्ग है जिनके बहुपद समय सत्यापनकर्ताओं को केवल उनके प्रमाण पत्र के रूप में खाली स्ट्रिंग प्राप्त करने की आवश्यकता होती है ), यह ज्ञात नहीं है कि NP Pसे सख्ती से बड़ा है या नहीं। यदि P= NP, तो यह इस प्रकार है कि किसी समस्या का समाधान जल्दी से खोजने की क्षमता के संबंध में नियतत्ववाद पर 'कोई अतिरिक्त कम्प्यूटेशनल शक्ति' प्रदान नहीं करता है; अर्थात्, संगणना की सभी संभावित शाखाओं का पता लगाने में सक्षम होने से केवल एक शाखा का पता लगाने में सक्षम होने पर एक बहुपद गति प्रदान करता है। इसके अतिरिक्त, यह अनुसरण करेगा कि यदि किसी समस्या के उदाहरण के लिए कोई प्रमाण उपस्थित है और उस प्रमाण को शुद्धता के लिए जल्दी से जांचा जा सकता है (अर्थात, यदि समस्या NP में है), तो एक एल्गोरिथ्म भी उपस्थित है जो जल्दी से 'निर्माण' कर सकता है ' वह प्रमाण (अर्थात समस्या P में है)। चुकीं, कंप्यूटर वैज्ञानिकों के विशाल बहुमत का मानना ​​है कि P$\neq$NP, और अधिकांश क्रिप्टोग्राफी # आज की आधुनिक क्रिप्टोग्राफी इस धारणा पर निर्भर करती है कि P$\neq$NP है.

EXPTIME और नेक्सपीटाइम

Main articles: एक्सपटाइम and नेक्सपीटाइम

EXPTIME (कभी-कभी EXP के रूप में संक्षिप्त) निर्णयात्मक समस्याओं का वर्ग है जिसे घातीय समय में नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है और नेक्सपीटाइम (कभी-कभी NEXP के रूप में छोटा किया जाता है) घातीय समय में एक गैर-नियतात्मक ट्यूरिंग मशीन द्वारा हल की जाने वाली निर्णय समस्याओं का वर्ग है। या अधिक औपचारिक रूप से,

${\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(2^{n^{k}})$

${\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})$

EXPTIME P का सख्त सुपर समुच्चय है और नेक्सपीटाइम NP का सख्त सुपर समुच्चय है। आगे यह स्थिति है कि EXPTIME$\subseteq$अगला। यह ज्ञात नहीं है कि यह उचित है या नहीं, लेकिन यदि P = NP तो EXPTIME को नेक्सपीटाइम के ​​बराबर होना चाहिए।

अंतरिक्ष जटिलता वर्ग

Main article: अंतरिक्ष जटिलता

L और NL

Main articles: L (जटिलता) and NL (जटिलता)

जबकि लॉगरिदमिक विकास समय जटिलता वर्गों को परिभाषित करना संभव है, ये अत्यंत संकीर्ण वर्ग हैं क्योंकि सबलाइनियर समय एक ट्यूरिंग मशीन को पूरे इनपुट को पढ़ने में सक्षम नहीं करता है (क्योंकि $\log n<n$). चुकीं, समस्याओं की सार्थक संख्या है जिन्हें लघुगणकीय स्थान में हल किया जा सकता है। इन वर्गों की परिभाषाओं के लिए एक मल्टीटेप ट्यूरिंग मशीन की आवश्यकता होती है | -टेप ट्यूरिंग मशीन)। दो-टेप ट्यूरिंग मशीन मॉडल में, एक टेप इनपुट टेप है, जो केवल पढ़ने के लिए है। दूसरा कार्य टेप है, जो पढ़ने और लिखने दोनों की अनुमति देता है और वह टेप है जिस पर ट्यूरिंग मशीन अभिकलन करती है। ट्यूरिंग मशीन की अंतरिक्ष जटिलता को कार्य टेप पर उपयोग की जाने वाली कोशिकाओं की संख्या के रूप में मापा जाता है।

L (कभी-कभी लागस्पेस तक लंबा) को नियतात्मक ट्यूरिंग मशीन पर लघुगणकीय स्थान में हल करने योग्य समस्याओं के वर्ग के रूप में परिभाषित किया जाता है और NL (कभी-कभी एनलॉगस्पेस तक लंबा) एक गैर-नियतात्मक ट्यूरिंग मशीन पर लघुगणकीय स्थान में हल करने योग्य समस्याओं का वर्ग होता है। या अधिक औपचारिक रूप से,

${\mathsf {L}}={\mathsf {DSPACE}}(\log n)$

${\mathsf {NL}}={\mathsf {NSPACE}}(\log n)$

ज्ञात है कि ${\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {P}}$. चुकीं, यह ज्ञात नहीं है कि इनमें से कोई भी संबंध उचित है या नहीं।

पीएसपीएसीई और एनपीस्पेस

Main article: पी स्पेस(जटिलता)

जटिलता वर्ग पीएसपीएसीई और एनपीएसपीएसीई P(जटिलता) और NP(जटिलता) के अंतरिक्ष अनुरूप हैं। अर्थात्, PSPACE नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद स्थान में हल की जाने वाली समस्याओं का वर्ग है और NPSPACE एक गैर-नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद स्थान में हल की जाने वाली समस्याओं का वर्ग है। अधिक औपचारिक रूप से,

${\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})$

${\mathsf {NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$

चुकीं यह ज्ञात नहीं है कि P=NP, सैविच के प्रमेय ने प्रसिद्ध रूप से दिखाया कि पीएसपीएसीई = एनपीएसपीएसीई। यह भी ज्ञात है कि P$\subseteq$PSPACE, जो इस तथ्य से सहज रूप से अनुसरण करता है कि, चूंकि ट्यूरिंग मशीन के टेप पर एक सेल को लिखना समय की एक इकाई लेने के रूप में परिभाषित किया गया है, बहुपद समय में संचालित एक ट्यूरिंग मशीन केवल बहुपद रूप से कई कोशिकाओं को लिख सकती है। ऐसा संदेह है कि P, PSPACE से सख्ती से छोटा है, लेकिन यह सिद्ध नहीं हुआ है।

एक्सपस्पेस और नेक्सस्पेस

Main article: एक्सपस्पेस

जटिलता वर्ग EXPSPACE और NEXPSPACE, EXPTIME और नेक्सपीटाइम के ​​स्पेस अनुरूप हैं। यही है, EXPSPACE नियतात्मक ट्यूरिंग मशीन द्वारा घातीय स्थान में हल की जाने वाली समस्याओं का वर्ग है और NEXPSPACE एक गैर-नियतात्मक ट्यूरिंग मशीन द्वारा घातीय स्थान में हल की जाने वाली समस्याओं का वर्ग है। या अधिक औपचारिक रूप से,

${\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})$

${\mathsf {NEXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$

सैविच के प्रमेय ने दिखाया कि EXPSPACE = NEXPSPACE। यह वर्ग अत्यंत व्यापक है: इसे PSPACE, NP, और P के सख्त सुपर समुच्चय के रूप में जाना जाता है, और माना जाता है कि यह EXPTIME का सख्त सुपर समुच्चय है।

जटिलता वर्गों के गुण

क्लोजर

जटिलता वर्गों में विभिन्न प्रकार के क्लोजर (गणित) गुण होते हैं। उदाहरण के लिए, निर्णय वर्ग निषेध, संयोजन, तार्किक संयोजन, या यहां तक ​​कि सभी तार्किक संयोजन के अंतर्गत बंद हो सकते हैं। इसके अतिरिक्त, वे विभिन्न परिमाणीकरण योजनाओं के अंतर्गत भी बंद हो सकते हैं। उदाहरण के लिए, P, सभी बूलियन परिचालनों के अंतर्गत बंद है, और बहुपद आकार वाले डोमेन पर क्वांटिफिकेशन के अंतर्गत बंद है। क्लोजर गुण वर्गों को अलग करने में सहायतागार हो सकते हैं - दो जटिलता वर्गों को अलग करने का एक संभावित मार्ग एक वर्ग के पास उपस्थित कुछ क्लोजर प्रॉपर्टी को खोजना है, लेकिन दूसरे के पास नहीं।

प्रत्येक कक्षा X जो निषेध के अंतर्गत बंद नहीं है, एक पूरक वर्ग सह-X है, जिसमें X में निहित भाषाओं के पूरक होते हैं (अर्थात सह-X =$\{L|{\overline {L}}\in$ X $\}$). सह-NP, उदाहरण के लिए, एक महत्वपूर्ण पूरक जटिलता वर्ग है, और सह-NP= NP पर अनसुलझी समस्या के केंद्र में बैठता है।

क्लोजर गुण प्रमुख कारणों में से एक हैं क्योंकि कई जटिलता वर्गों को उनके रूप में परिभाषित किया गया है। उदाहरण के लिए, एक ऐसी समस्या को लीजिए, जिसका हल निकाला जा सकता है $O(n)$ समय (अर्थात, रैखिक समय में) और एक जिसे सबसे अच्छे से हल किया जा सकता है, $O(n^{1000})$ समय। ये दोनों समस्याएं P में हैं, फिर भी दूसरे का रनटाइम पहले के रनटाइम की तुलना में काफी तेजी से बढ़ता है क्योंकि इनपुट का आकार बढ़ता है। कोई यह पूछ सकता है कि क्या कुछ छोटी बहुपद सीमाओं का उपयोग करके कुशलतापूर्वक हल करने योग्य समस्याओं के वर्ग को परिभाषित करना बेहतर होगा, जैसे $O(n^{3})$, सभी बहुपदों के अतिरिक्त, जो इतनी बड़ी विसंगतियों की अनुमति देता है। चुकीं, यह पता चला है कि सभी बहुपदों का समुच्चय, रैखिक कार्यों वाले कार्यों का सबसे छोटा वर्ग है, जो कि जोड़, गुणा और संरचना के अंतर्गत भी बंद है (उदाहरण के लिए, $O(n^{3})\circ O(n^{2})=O(n^{6})$, जो एक बहुपद है लेकिन $O(n^{6})>O(n^{3})$). चूंकि हम अभी भी कुशल माने जाने के लिए एक अन्य कुशल एल्गोरिथ्म के साथ एक कुशल एल्गोरिथ्म की रचना करना चाहते हैं, बहुपद सबसे छोटा वर्ग है जो कुशल एल्गोरिदम की संरचना सुनिश्चित करता है। (ध्यान दें कि P की परिभाषा भी उपयोगी है क्योंकि अनुभवजन्य रूप से, Pमें लगभग सभी समस्याएं जो व्यावहारिक रूप से उपयोगी हैं, वास्तव में निम्न क्रम बहुपद रनटाइम हैं, और P के बाहर लगभग सभी समस्याएं जो व्यावहारिक रूप से उपयोगी हैं, उनके पास कोई ज्ञात एल्गोरिदम नहीं है छोटे घातीय रनटाइम के साथ, यानी के साथ $O(c^{n})$ रनटाइम जहाँ $c$ 1 के समीप है।)

कटौती

See also: कमी (जटिलता)

कमी की अवधारणा का उपयोग करके कई जटिलता वर्गों को परिभाषित किया गया है। एक कमी एक समस्या का दूसरी समस्या में रूपांतरण है, यानी कमी एक समस्या से इनपुट लेती है और उन्हें दूसरी समस्या के इनपुट में बदल देती है। उदाहरण के लिए, आप साधारण आधार-10 जोड़ को कम कर सकते हैं $x+y$ आधार -2 के अतिरिक्त रूपांतरण द्वारा $x$ और $y$ उनके आधार -2 अंकन के लिए (जैसे 5+7 101+111 बन जाता है)। औपचारिक रूप से, एक समस्या $X$ समस्या को कम करता है $Y$ अगर कोई फलन उपस्थित है $f$ ऐसा कि प्रत्येक के लिए $x\in \Sigma ^{*}$, $x\in X$ अगर और केवल अगर $f(x)\in Y$है

सामान्यतः , कटौती का उपयोग किसी समस्या की धारणा को पकड़ने के लिए किया जाता है जो कम से कम दूसरी समस्या के रूप में कठिन हो। इस प्रकार हम सामान्यतः किसी भी समस्या के बाद बहुपद-समय में कमी का उपयोग करने में रुचि रखते हैं $X$ जिसे कुशलता से दूसरी समस्या में कम किया जा सकता है $Y$ से अधिक कठिन नहीं है $Y$. औपचारिक रूप से, एक समस्या $X$ एक समस्या के लिए बहुपद-समय कम करने योग्य है $Y$ यदि कोई बहुपद-समय संगणनीय कार्य उपस्थित है $p$ ऐसा कि सभी के लिए $x\in \Sigma ^{*}$, $x\in X$ अगर और केवल अगर $p(x)\in Y$ है

ध्यान दें कि कटौती को कई अलग-अलग विधियों से परिभाषित किया जा सकता है। सामान्य कटौती कुक कटौती, कार्प कटौती और लेविन कटौती हैं, और संसाधन सीमाओं के आधार पर भिन्न हो सकती हैं, जैसे बहुपद-समय में कटौती और लॉग-स्पेस कटौती है।

कठोरता

कटौती एक जटिलता वर्ग के लिए एक समस्या के कठिन होने की अवधारणा को प्रेरित करती है। एक समस्या $X$ समस्याओं के एक वर्ग C के लिए कठिन है यदि C में प्रत्येक समस्या को बहुपद-समय तक कम किया जा सकता है $X$. इस प्रकार C में कोई समस्या कठिन नहीं है $X$, क्योंकि एक एल्गोरिथ्म के लिए $X$ हमें C में किसी भी समस्या को हल करने की अनुमति देता है जिसमें अधिकांश बहुपद मंदी होती है। विशेष रूप से, NP के लिए कठिन समस्याओं के समुच्चयको NP कठिन समस्याओं का समुच्चय कहा जाता है।

संपूर्णता

अगर कोई समस्या है $X$ C के लिए कठिन है और C में भी है, तब $X$ C. के लिए पूर्ण (जटिलता) कहा जाता है। इसका अर्थ है कि $X$ C में सबसे कठिन समस्या है (चूंकि ऐसी कई समस्याएं हो सकती हैं जो समान रूप से कठिन हों, अधिक सटीक रूप से $X$ C में सबसे कठिन समस्या जितनी कठिन है)।

NPनप -पूर्ण | एनपी-पूर्ण समस्याओं का वर्ग विशेष महत्व का है- NPमें सबसे कठिन समस्याएं। क्योंकि NP में सभी समस्याएं बहुपद-समय को एनपी-पूर्ण समस्याओं में घटाया जा सकता है, एक NP-पूर्ण समस्या को बहुपद समय में हल करने का अर्थ होगा कि P= NP है।

जटिलता वर्गों के बीच संबंध

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

Main article: सैविच की प्रमेय

सैविच की प्रमेय नियतात्मक और गैर-नियतात्मक अंतरिक्ष संसाधनों के बीच संबंध स्थापित करती है। यह दर्शाता है कि यदि एक गैर-नियतात्मक ट्यूरिंग मशीन किसी समस्या का समाधान कर सकती है $f(n)$ अंतरिक्ष, तो एक नियतात्मक ट्यूरिंग मशीन उसी समस्या को हल कर सकती है $f(n)^{2}$ अंतरिक्ष, यानी अंतरिक्ष के वर्ग में। औपचारिक रूप से, सैविच के प्रमेय में कहा गया है कि किसी के लिए भी $f(n)>n$ है,

${\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right).$

सैविच के प्रमेय के महत्वपूर्ण परिणाम हैं कि PSPACE = NPSPACE (चूंकि एक बहुपद का वर्ग अभी भी एक बहुपद है) और EXPSPACE = NEXPSPACE (चूंकि एक घातांक का वर्ग अभी भी एक घातीय है)।

ये रिश्ते नियतत्ववाद की तुलना में गैर-नियतत्ववाद की शक्ति के बारे में मूलभूत प्रश्नों का उत्तर देते हैं। विशेष रूप से, सैविच के प्रमेय से पता चलता है कि कोई भी समस्या जो एक गैर-नियतात्मक ट्यूरिंग मशीन बहुपद अंतरिक्ष में हल कर सकती है, एक नियतात्मक ट्यूरिंग मशीन भी बहुपद अंतरिक्ष में हल कर सकती है। इसी तरह, कोई भी समस्या जो एक गैर-नियतात्मक ट्यूरिंग मशीन एक्सपोनेंशियल स्पेस में हल कर सकती है, एक नियतात्मक ट्यूरिंग मशीन भी एक्सपोनेंशियल स्पेस में हल कर सकती है।

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

Main articles: समय पदानुक्रम प्रमेय and अंतरिक्ष पदानुक्रम प्रमेय

DTIME की परिभाषा के अनुसार, यह इस प्रकार है ${\mathsf {DTIME}}(n^{k_{1}})$ में निहित है ${\mathsf {DTIME}}(n^{k_{2}})$ अगर $k_{1}\leq k_{2}$, तब से $O(n^{k_{1}})\subseteq O(n^{k_{2}})$ अगर $k_{1}\leq k_{2}$. चुकीं, यह परिभाषा इस बात का कोई संकेत नहीं देती है कि यह समावेश सख्त है या नहीं। समय और स्थान की आवश्यकताओं के लिए, जिन शर्तों के अंतर्गत समावेश सख्त है, उन्हें क्रमशः समय और स्थान पदानुक्रम प्रमेय द्वारा दिया जाता है। उन्हें पदानुक्रम प्रमेय कहा जाता है क्योंकि वे संबंधित संसाधनों को बाधित करके परिभाषित वर्गों पर उचित पदानुक्रम उत्पन्न करते हैं। पदानुक्रम प्रमेय किसी को मात्रात्मक बयान देने में सक्षम बनाता है कि हल की जा सकने वाली समस्याओं की संख्या बढ़ाने के लिए कितना अतिरिक्त समय या स्थान आवश्यक है।

समय पदानुक्रम प्रमेय कहता है कि

${\mathsf {DTIME}}{\big (}f(n){\big )}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log ^{2}(f(n)){\big )}$.

अंतरिक्ष पदानुक्रम प्रमेय कहता है कि

${\mathsf {DSPACE}}{\big (}f(n){\big )}\subsetneq {\mathsf {DSPACE}}{\big (}f(n)\cdot \log(f(n)){\big )}$.

समय और स्थान पदानुक्रम प्रमेय जटिलता वर्गों के अधिकांश पृथक्करण परिणामों का आधार बनाते हैं। उदाहरण के लिए, समय पदानुक्रम प्रमेय स्थापित करता है कि P EXPTIME में कड़ाई से समाहित है, और अंतरिक्ष पदानुक्रम प्रमेय स्थापित करता है कि L सख्ती से PSPACE में समाहित है।

संगणना के अन्य मॉडल

जबकि नियतात्मक और गैर-नियतात्मक ट्यूरिंग मशीन गणना के सबसे अधिक उपयोग किए जाने वाले मॉडल हैं, कई जटिलता वर्गों को अन्य कम्प्यूटेशनल मॉडल के संदर्भ में परिभाषित किया गया है। विशेष रूप से,

• संभाव्य ट्यूरिंग मशीनों का उपयोग करके कई वर्गों को परिभाषित किया गया है, जिसमें कक्षाएं बाउंड-त्रुटि संभाव्य बहुपद, PP(जटिलता), RP(जटिलता), और ZPP(जटिलता) सम्मिलित हैं।
• IP(जटिलता), MA (जटिलता), और MA (जटिलता) सहित इंटरएक्टिव प्रूफ प्रणाली का उपयोग करके कई वर्गों को परिभाषित किया गया है।
• बूलियन सर्किट का उपयोग करके कई वर्गों को परिभाषित किया गया है, जिसमें वर्ग P/POLY और इसके उपवर्ग NC (जटिलता) और AC (जटिलता) सम्मिलित हैं।
• BQPऔर QMA कक्षाओं सहित क्वांटम ट्यूरिंग मशीनों का उपयोग करके कई वर्गों को परिभाषित किया गया है

इन्हें नीचे और अधिक विस्तार से समझाया गया है।

यादृच्छिक संगणना

Main article: यादृच्छिक संगणना

संभाव्य ट्यूरिंग मशीन का उपयोग करके कई महत्वपूर्ण जटिलता वर्गों को परिभाषित किया गया है, ट्यूरिंग मशीन का एक प्रकार जो यादृच्छिक सिक्कों को टॉस कर सकता है। ये कक्षाएं यादृच्छिक एल्गोरिदम की जटिलता का बेहतर वर्णन करने में सहायता करती हैं।

एक संभाव्य ट्यूरिंग मशीन एक नियतात्मक ट्यूरिंग मशीन के समान है, केवल एक ट्रांज़िशन फलन (कम्प्यूटेशन के प्रत्येक चरण पर आगे बढ़ने के लिए नियमों का एक सेट) का पालन करने के अतिरिक्त यह संभावित रूप से प्रत्येक चरण में कई ट्रांज़िशन फलन के बीच चयन करता है। संभाव्य ट्यूरिंग मशीन की मानक परिभाषा दो संक्रमण कार्यों को निर्दिष्ट करती है, ताकि प्रत्येक चरण पर संक्रमण फलन का चयन एक सिक्का फ्लिप जैसा दिखता हो। संगणना के प्रत्येक चरण में प्रारंभ की गई यादृच्छिकता त्रुटि की संभावना का परिचय देती है; अर्थात्, स्ट्रिंग्स जो ट्यूरिंग मशीन को स्वीकार करने के लिए होती हैं, कुछ अवसरों पर अस्वीकार की जा सकती हैं और स्ट्रिंग्स जो ट्यूरिंग मशीन को अस्वीकार करने के लिए होती हैं, कुछ अवसरों पर स्वीकार की जा सकती हैं। नतीजतन, संभाव्य ट्यूरिंग मशीन पर आधारित जटिलता वर्गों को अनुमत त्रुटि की मात्रा के आसपास बड़े भाग में परिभाषित किया गया है। औपचारिक रूप से, उन्हें एक त्रुटि संभावना का उपयोग करके परिभाषित किया गया है $\epsilon$. एक संभाव्य ट्यूरिंग मशीन $M$ एक भाषा को पहचानने के लिए कहा जाता है $L$ त्रुटि संभावना के साथ $\epsilon$ अगर:

1. एक स्ट्रिंग $w$ में $L$ इसका आशय है ${\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon$
2. एक स्ट्रिंग $w$ अंदर नही $L$ इसका आशय है ${\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon$

महत्वपूर्ण जटिलता वर्ग

Error creating thumbnail:

मौलिक संभाव्य जटिलता वर्गों के बीच संबंध। बीक्यूPएक संभाव्य क्वांटम जटिलता सिद्धांत वर्ग है और क्वांटम कंप्यूटिंग अनुभाग में वर्णित है।

मौलिक यादृच्छिक समय जटिलता वर्ग ZPP (जटिलता), RP (जटिलता), सह-RP, BPP (जटिलता), और PP (जटिलता) हैं।

सबसे सख्त वर्ग ZPP (जटिलता) (शून्य-त्रुटि संभाव्य बहुपद समय) है, त्रुटि संभाव्यता 0 के साथ एक संभाव्य ट्यूरिंग मशीन द्वारा बहुपद समय में हल की जाने वाली समस्याओं का वर्ग। सहज रूप से, यह संभाव्य समस्याओं का सबसे सख्त वर्ग है क्योंकि यह मांग करता है कोई त्रुटि नहीं।

थोड़ा ढीला वर्ग RP(जटिलता) (यादृच्छिक बहुपद समय) है, जो भाषा में तारों के लिए कोई त्रुटि नहीं रखता है लेकिन भाषा में तारों के लिए बाध्य त्रुटि की अनुमति देता है। अधिक औपचारिक रूप से, एक भाषा RPमें है यदि कोई संभाव्य बहुपद-समय ट्यूरिंग मशीन है $M$ ऐसा है कि यदि कोई स्ट्रिंग भाषा में नहीं है तो $M$ हमेशा अस्वीकार करता है और यदि कोई स्ट्रिंग भाषा में है तो $M$ संभावना के साथ कम से कम 1/2 स्वीकार करता है। वर्ग सह-आरPको समान रूप से परिभाषित किया गया है, सिवाय इसके कि भूमिकाएँ फ़्लिप की जाती हैं: भाषा में स्ट्रिंग्स के लिए त्रुटि की अनुमति नहीं है, लेकिन भाषा में स्ट्रिंग्स के लिए अनुमति नहीं है। एक साथ लिया गया, कक्षाएं RPऔर सह-RPउन सभी समस्याओं को सम्मिलित करती हैं जिन्हें एकतरफा त्रुटि के साथ संभाव्य ट्यूरिंग मशीनों द्वारा हल किया जा सकता है।

दो तरफा त्रुटि की अनुमति देने के लिए त्रुटि आवश्यकताओं को और ढीला करने से वर्ग BPP(जटिलता) (परिबद्ध-त्रुटि संभाव्य बहुपद समय) प्राप्त होता है, एक संभाव्यता ट्यूरिंग मशीन द्वारा बहुपद समय में हल की जाने वाली समस्याओं का वर्ग 1/3 से कम त्रुटि संभावना के साथ ( भाषा में दोनों तारों के लिए और भाषा में नहीं)। BPPसंभाव्य जटिलता वर्गों का सबसे व्यावहारिक रूप से प्रासंगिक है- BPPमें समस्याओं में कुशल यादृच्छिक एल्गोरिदम हैं जो वास्तविक कंप्यूटरों पर जल्दी से चलाए जा सकते हैं। BPP कंप्यूटर विज्ञान में महत्वपूर्ण अनसुलझी समस्या के केंद्र में भी है कि क्या BPP है (जटिलता)#Problems| P=BPP, जो अगर सच है तो इसका अर्थ होगा कि यादृच्छिकता कंप्यूटर की कम्प्यूटेशनल शक्ति को नहीं बढ़ाती है, यानी कोई भी संभावित ट्यूरिंग मशीन हो सकती है अधिकांश बहुपद मंदी के साथ नियतात्मक ट्यूरिंग मशीन द्वारा सिम्युलेटेड है।

कुशलता से हल करने योग्य संभाव्य समस्याओं का सबसे व्यापक वर्ग PP(जटिलता) (संभाव्य बहुपद समय) है, सभी स्ट्रिंग्स के लिए 1/2 से कम की त्रुटि संभावना के साथ बहुपद समय में एक संभाव्य ट्यूरिंग मशीन द्वारा हल करने योग्य भाषाओं का सेट है।

ZPP, RP और Co-RP सभी BPP के उपसमुच्चय हैं, जो बदले में PP का उपसमुच्चय है। इसका कारण सहज है: शून्य त्रुटि और केवल एक तरफा त्रुटि की अनुमति देने वाली कक्षाएं उस वर्ग के अन्दर समाहित हैं जो दो तरफा त्रुटि की अनुमति देता है, और PPकेवल BPPकी त्रुटि संभावना को कम करता है। ZPP निम्नलिखित विधियों से RP और Co-RP से संबंधित है: ${\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}$. अर्थात्, ZPP में ठीक वही समस्याएँ होती हैं जो RP और सह-RP दोनों में होती हैं। सहज रूप से, यह इस तथ्य से अनुसरण करता है कि आरPऔर सह-RPकेवल एक तरफा त्रुटि की अनुमति देते हैं: सह-RPभाषा में स्ट्रिंग्स के लिए त्रुटि की अनुमति नहीं देता है और RरPभाषा में स्ट्रिंग्स के लिए त्रुटि की अनुमति नहीं देता है। इसलिए, यदि कोई समस्या RPऔर सह-RPदोनों में है, तो स्ट्रिंग्स के लिए और दोनों में कोई त्रुटि नहीं होनी चाहिए, न कि भाषा में (अर्थात कोई त्रुटि नहीं), जो वास्तव में ZPP की परिभाषा है।

महत्वपूर्ण यादृच्छिक अंतरिक्ष जटिलता वर्गों में बीपीएल (जटिलता), आरएल (जटिलता), और यादृच्छिक लॉगरिदमिक-स्पेस बहुपद-समय सम्मिलित हैं।

इंटरएक्टिव प्रूफ प्रणाली

Main article: इंटरएक्टिव प्रूफ प्रणाली

इंटरैक्टिव प्रूफ प्रणाली का उपयोग करके कई जटिलता वर्गों को परिभाषित किया गया है। इंटरएक्टिव सबूत जटिलता वर्ग NP(जटिलता) की सबूत परिभाषा को सामान्यीकृत करते हैं और क्रिप्टोग्राफी, सन्निकटन एल्गोरिदम और औपचारिक सत्यापन में अंतर्दृष्टि प्रदान करते हैं।

File:Interactive proof (complexity).svg

इंटरएक्टिव प्रूफ प्रोटोकॉल का सामान्य प्रतिनिधित्व

इंटरएक्टिव प्रूफ प्रणाली अमूर्त मशीनें हैं जो दो पक्षों के बीच संदेशों के आदान-प्रदान के रूप में मॉडल की गणना करती हैं: एक कहावत $P$ और एक सत्यापनकर्ता $V$. पार्टियां संदेशों का आदान-प्रदान करके बातचीत करती हैं, और एक इनपुट स्ट्रिंग प्रणाली द्वारा स्वीकार की जाती है यदि सत्यापनकर्ता प्रोवर से प्राप्त संदेशों के आधार पर इनपुट को स्वीकार करने का निर्णय लेता है। कहावत $P$ असीमित कम्प्यूटेशनल शक्ति है जबकि सत्यापनकर्ता ने कम्प्यूटेशनल शक्ति को सीमित कर दिया है (इंटरैक्टिव प्रूफ प्रणाली की मानक परिभाषा सत्यापनकर्ता को बहुपद-समयबद्ध होने के लिए परिभाषित करती है)। चुकीं, कहावत अविश्वसनीय है (यह सभी भाषाओं को प्रूफ प्रणाली द्वारा तुच्छ रूप से मान्यता प्राप्त होने से रोकता है, कम्प्यूटेशनल रूप से अनबाउंड प्रोवर हल करता है कि क्या एक स्ट्रिंग एक भाषा में है और फिर सत्यापनकर्ता को एक विश्वसनीय हाँ या नहीं भेज रहा है), इसलिए सत्यापनकर्ता को प्रोवर से सवालों के लगातार दौर पूछकर उससे पूछताछ करनी चाहिए, केवल यह स्वीकार करते हुए कि वह उच्च स्तर का विश्वास विकसित करता है कि स्ट्रिंग भाषा में है।

महत्वपूर्ण जटिलता वर्ग

वर्ग NP(जटिलता) एक साधारण प्रमाण प्रणाली है जिसमें सत्यापनकर्ता नियतात्मक बहुपद-समय ट्यूरिंग मशीन होने तक सीमित है और प्रक्रिया एक दौर तक ही सीमित है (अर्थात, कहावत केवल एक एकल, पूर्ण प्रमाण भेजती है - सामान्यतः संदर्भित प्रमाणपत्र के रूप में (जटिलता)—सत्यापनकर्ता के लिए)। एक और विधि रखो, वर्ग NP की परिभाषा में (निर्णय समस्याओं का समुच्चयजिसके लिए समस्या का उदाहरण है, जब उत्तर हाँ है, एक नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में सत्यापन योग्य प्रमाण हैं) एक प्रमाण प्रणाली है जिसमें प्रमाण है एक अज्ञात प्रोवर द्वारा निर्मित और नियतात्मक ट्यूरिंग मशीन सत्यापनकर्ता है। इस कारण से, NPको DIP (नियतात्मक इंटरैक्टिव सबूत) भी कहा जा सकता है, चुकीं इसे शायद ही कभी ऐसा कहा जाता है।

यह पता चला है कि NP नियतात्मक (बहुपद-समय) सत्यापनकर्ताओं के साथ इंटरैक्टिव प्रूफ प्रणाली की पूरी शक्ति पर कब्जा कर लेता है क्योंकि यह दिखाया जा सकता है कि किसी नियतात्मक सत्यापनकर्ता के साथ किसी भी प्रूफ प्रणाली के लिए संदेश के बीच एक से अधिक राउंड की आवश्यकता नहीं होती है। समर्थक और सत्यापनकर्ता। इंटरएक्टिव प्रूफ प्रणाली जो मानक जटिलता वर्गों पर अधिक कम्प्यूटेशनल शक्ति प्रदान करते हैं, इस प्रकार 'संभाव्य' सत्यापनकर्ता की आवश्यकता होती है, जिसका अर्थ है कि सत्यापनकर्ता के सवालों की गणना संभाव्य एल्गोरिदम का उपयोग करके की जाती है। जैसा कि रेंडमाइज्ड संगणना पर ऊपर दिए गए खंड में उल्लेख किया गया है, संभाव्य एल्गोरिदम प्रणाली में त्रुटि का परिचय देते हैं, इसलिए संभाव्यता प्रूफ प्रणाली पर आधारित जटिलता वर्ग त्रुटि संभाव्यता के संदर्भ में परिभाषित किए गए हैं। $\epsilon$.

इस लक्षण वर्णन से उत्पन्न होने वाली सबसे सामान्य जटिलता वर्ग IP (जटिलता) (इंटरैक्टिव बहुपद समय) है, जो एक इंटरैक्टिव प्रूफ प्रणाली द्वारा हल की जाने वाली सभी समस्याओं का वर्ग है। $(P,V)$, जहाँ $V$ संभाव्य बहुपद-समय है और प्रमाण प्रणाली दो गुणों को संतुष्ट करती है: एक भाषा के लिए $L\in {\mathsf {IP}}$ है

1. (पूर्णता) एक स्ट्रिंग $w$ में $L$ तात्पर्य $\Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\geq {\tfrac {2}{3}}$
2. (साउंडनेस) एक स्ट्रिंग $w$ अंदर नही $L$ तात्पर्य $\Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\leq {\tfrac {1}{3}}$

IP की एक महत्वपूर्ण विशेषता यह है कि यह PSPACE के बराबर है। दूसरे शब्दों में, किसी भी समस्या को बहुपद-समय के इंटरएक्टिव प्रूफ प्रणाली द्वारा हल किया जा सकता है, जिसे नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद अंतरिक्ष संसाधनों के साथ हल किया जा सकता है, और इसके विपरीत है।

IP​​​​के लिए प्रोटोकॉल का एक संशोधन एक और महत्वपूर्ण जटिलता वर्ग उत्पन करता है: AAM (जटिलता) (आर्थर-मर्लिन प्रोटोकॉल)। IP​​​​द्वारा उपयोग किए जाने वाले इंटरएक्टिव प्रूफ प्रणाली की परिभाषा में, प्रोवर अपनी संभाव्य गणना में सत्यापनकर्ता द्वारा उपयोग किए गए सिक्कों को देखने में सक्षम नहीं था - यह केवल उन संदेशों को देखने में सक्षम था जो सत्यापनकर्ता ने इन सिक्कों के साथ उत्पादित किए थे। इस कारण से, सिक्कों को निजी यादृच्छिक सिक्के कहा जाता है। इंटरएक्टिव प्रूफ प्रणाली को विवश किया जा सकता है ताकि सत्यापनकर्ता द्वारा उपयोग किए जाने वाले सिक्के सार्वजनिक यादृच्छिक सिक्के हों; अर्थात्, कहावत सिक्के देखने में सक्षम है। औपचारिक रूप से, एएम को एक इंटरैक्टिव प्रमाण के साथ भाषाओं की श्रेणी के रूप में परिभाषित किया जाता है जिसमें सत्यापनकर्ता प्रोवर को एक यादृच्छिक स्ट्रिंग भेजता है, प्रोवर एक संदेश के साथ प्रतिक्रिया करता है, और सत्यापनकर्ता या तो निर्धारक बहुपद-समय फलन को प्रयुक्त करके स्वीकार या अस्वीकार करता है। कहावत से संदेश। AAM को AAM [K] के लिए सामान्यीकृत किया जा सकता है, जहां K एक्सचेंज किए गए संदेशों की संख्या है (इसलिए सामान्यीकृत रूप में ऊपर परिभाषित मानक AAM [2] है)। चुकीं, यह सभी के लिए है $k\geq 2$, AM[k]=AM[2]. आलम यह भी है कि ${\mathsf {AM}}[k]\subseteq {\mathsf {IP}}[k]$.

इंटरएक्टिव प्रूफ प्रणाली का उपयोग करके परिभाषित अन्य जटिलता वर्गों में इंटरएक्टिव प्रूफ प्रणाली # MIP (मल्टीप्रोवर इंटरएक्टिव बहुपद समय) और QIP (जटिलता) (क्वांटम इंटरैक्टिव बहुपद समय) सम्मिलित हैं।

बूलियन सर्किट

Main article: सर्किट जटिलता

[[/index.php?title=Special:MathShowImage&hash=0b6c75bd3067049ffe8774cbadcb3bc0&mode=mathml|thumb|right|बूलियन फलन की गणना करने वाले बूलियन सर्किट का उदाहरण $f_{C}(x_{1},x_{2},x_{3})=\neg (x_{1}\wedge x_{2})\wedge ((x_{2}\wedge x_{3})\vee \neg x_{3})$, उदाहरण इनपुट के साथ $x_{1}=0$, $x_{2}=1$, और $x_{3}=0$. $\wedge$ h> नोड AND गेट्स हैं, द $\vee$ नोड या द्वार हैं, और $\neg$ गेट नहीं नहीं हैं।|link=|alt={\displaystyle f_{C}(x_{1},x_{2},x_{3})=\neg (x_{1}\wedge x_{2})\wedge ((x_{2}\wedge x_{3})\vee \neg x_{3})}]]ट्यूरिंग मशीन की संगणना का एक वैकल्पिक मॉडल बूलियन सर्किट है, जो आधुनिक कंप्यूटरों में उपयोग किए जाने वाले डिजिटल सर्किट का एक सरलीकृत मॉडल है। यह मॉडल न केवल सिद्धांत में गणना और व्यवहार में गणना के बीच एक सहज संबंध प्रदान करता है, बल्कि यह गैर-समान गणना के लिए एक प्राकृतिक मॉडल भी है (गणना जिसमें एक ही समस्या के अन्दर विभिन्न इनपुट आकार अलग-अलग एल्गोरिदम का उपयोग करते हैं)।

औपचारिक रूप से, एक बूलियन सर्किट $C$ एक निर्देशित अचक्रीय ग्राफ है जिसमें किनारे तारों का प्रतिनिधित्व करते हैं (जो बिट मान 0 और 1 ले जाते हैं), इनपुट बिट्स को स्रोत वर्टिकल (बिना आने वाले किनारों वाले कोने) द्वारा दर्शाया जाता है, और सभी गैर-स्रोत कोने लॉजिक गेट्स का प्रतिनिधित्व करते हैं (सामान्यतः AND) द्वार, या द्वार, और द्वार नहीं)। एक लॉजिक गेट को आउटपुट गेट कहा जाता है, और यह गणना के अंत का प्रतिनिधित्व करता है। सर्किट का इनपुट/आउटपुट व्यवहार $C$ साथ $n$ इनपुट चर बूलियन फलन द्वारा दर्शाए जाते हैं $f_{C}:\{0,1\}^{n}\to \{0,1\}$; उदाहरण के लिए, इनपुट बिट्स पर $x_{1},x_{2},...,x_{n}$, आउटपुट बिट $b$ सर्किट के रूप में गणितीय रूप से दर्शाया गया है $b=f_{C}(x_{1},x_{2},...,x_{n})$. सर्किट $C$ बूलियन फलन की गणना करने के लिए कहा जाता है $f_{C}$.

किसी विशेष सर्किट में निश्चित संख्या में इनपुट लंबवत होते हैं, इसलिए यह केवल उस आकार के इनपुट पर कार्य कर सकता है। औपचारिक भाषा (निर्णय समस्याओं का औपचारिक निरूपण), चुकीं, अलग-अलग लंबाई के तार होते हैं, इसलिए भाषाओं को एक सर्किट द्वारा पूरी तरह से कैप्चर नहीं किया जा सकता है (यह ट्यूरिंग मशीन मॉडल के विपरीत है, जिसमें एक भाषा पूरी तरह से एक ट्यूरिंग मशीन द्वारा वर्णित है) जो किसी भी इनपुट आकार पर कार्य कर सकता है)। एक भाषा इस प्रकार एक सर्किट परिवार द्वारा प्रस्तुत की जाती है। एक सर्किट परिवार सर्किट की अनंत सूची है $(C_{0},C_{1},C_{2},...)$, कहाँ $C_{n}$ के साथ एक सर्किट है $n$ इनपुट चर। कहा जाता है कि एक सर्किट परिवार एक भाषा तय करता है $L$ अगर, हर स्ट्रिंग के लिए $w$, $w$ भाषा में है $L$ अगर और केवल अगर $C_{n}(w)=1$, कहाँ $n$ की लम्बाई है $w$. दूसरे शब्दों में, एक स्ट्रिंग $w$ आकार का $n$ सर्किट परिवार द्वारा प्रस्तुत भाषा में है $(C_{0},C_{1},C_{2},...)$ अगर सर्किट $C_{n}$ (बिट्स की संख्या के रूप में इनपुट वर्टिकल की समान संख्या वाला सर्किट $w$) 1 का मूल्यांकन करता है जब $w$ इसका इनपुट है।

जबकि ट्यूरिंग मशीनों का उपयोग करके परिभाषित जटिलता वर्गों को समय जटिलता के संदर्भ में वर्णित किया गया है, सर्किट जटिलता वर्गों को सर्किट आकार - सर्किट में वर्टिकल की संख्या के संदर्भ में परिभाषित किया गया है। एक सर्किट परिवार की आकार जटिलता $(C_{0},C_{1},C_{2},...)$ कार्य है $f:\mathbb {N} \to \mathbb {N}$, कहाँ $f(n)$ का सर्किट आकार है $C_{n}$. परिचित कार्य वर्ग स्वाभाविक रूप से इसका अनुसरण करते हैं; उदाहरण के लिए, एक बहुपद-आकार का सर्किट परिवार एक ऐसा है जो कार्य करता है $f$ एक बहुपद है।

महत्वपूर्ण जटिलता वर्ग

जटिलता वर्ग पी/पॉली उन भाषाओं का समूह है जो बहुपद-आकार के सर्किट परिवारों द्वारा तय की जा सकती हैं। यह पता चला है कि सर्किट जटिलता और समय जटिलता के बीच एक स्वाभाविक संबंध है। सहज रूप से, कम समय की जटिलता वाली भाषा (यानी, ट्यूरिंग मशीन पर अपेक्षाकृत कुछ अनुक्रमिक संचालन की आवश्यकता होती है), इसमें एक छोटी सर्किट जटिलता भी होती है (अर्थात, अपेक्षाकृत कुछ बूलियन संचालन की आवश्यकता होती है)। औपचारिक रूप से, यह दिखाया जा सकता है कि यदि कोई भाषा में है ${\mathsf {DTIME}}(t(n))$, जहाँ $t$ एक कार्य है $t:\mathbb {N} \to \mathbb {N}$, तो इसमें सर्किट जटिलता है $O(t^{2}(n))$. यह इस तथ्य से सीधे अनुसरण करता है कि P (जटिलता) |${\mathsf {\color {Blue}P}}\subset {\textsf {P/poly}}$. दूसरे शब्दों में, नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में हल की जा सकने वाली किसी भी समस्या को बहुपद आकार के सर्किट परिवार द्वारा भी हल किया जा सकता है। आगे यह स्थिति है कि समावेशन उचित है, अर्थात ${\textsf {P}}\subsetneq {\textsf {P/poly}}$ (उदाहरण के लिए, कुछ अनिर्णीत समस्याएं हैं जो P/POLY में हैं)।

P/POLY में कई गुण हैं जो इसे जटिलता वर्गों के बीच संबंधों के अध्ययन में अत्यधिक उपयोगी बनाते हैं। विशेष रूप से, यह P बनाम NP से संबंधित समस्याओं की जाँच करने में सहायक है। उदाहरण के लिए, यदि NP में कोई ऐसी भाषा है जो P/POLY में नहीं है, तो ${\mathsf {P}}\neq {\mathsf {NP}}$. P/POLY बहुपद पदानुक्रम के गुणों की जांच करने में भी सहायक है। उदाहरण के लिए, यदि NP(जटिलता) ⊆ P/POLY, तो PH गिर जाता है $\Sigma _{2}^{\mathsf {P}}$. P/POLY और अन्य जटिलता वर्गों के बीच संबंधों का पूरा विवरण P/POLY# इसका महत्व P/polyp |I इसका महत्वP/poly पर उपलब्ध है। P/POLY ट्यूरिंग मशीनों के गुणों के सामान्य अध्ययन में भी सहायक है, क्योंकि कक्षा को बहुपद-समय ट्यूरिंग मशीन द्वारा बहुपद-सीमित सलाह (जटिलता) के साथ मान्यता प्राप्त भाषाओं के वर्ग के रूप में समान रूप से परिभाषित किया जा सकता है।

P/POLY के दो उपवर्ग जिनके अपने आप में दिलचस्प गुण हैं, NC (जटिलता) और AC (जटिलता) हैं। इन वर्गों को न केवल उनके सर्किट आकार के संदर्भ में बल्कि उनकी गहराई के संदर्भ में भी परिभाषित किया गया है। एक सर्किट की गहराई इनपुट नोड से आउटपुट नोड तक सबसे लंबे निर्देशित पथ की लंबाई है। वर्ग एनसी भाषाओं का समूह है जिसे सर्किट परिवारों द्वारा हल किया जा सकता है जो न केवल बहुपद-आकार तक ही सीमित हैं बल्कि बहुलगणकीय गहराई तक भी सीमित हैं। क्लास AC को NC के समान परिभाषित किया गया है, चुकीं गेट्स को अनबाउंड फैन-इन (यानी AND और OR गेट्स को दो से अधिक बिट्स पर प्रयुक्त किया जा सकता है) की अनुमति है। NC एक उल्लेखनीय वर्ग है क्योंकि इसे समान रूप से उन भाषाओं के वर्ग के रूप में परिभाषित किया जा सकता है जिनमें कुशल समानांतर एल्गोरिदम हैं।

क्वांटम गणना

BQPऔर QMA वर्ग, जो क्वांटम सूचना विज्ञान में महत्वपूर्ण हैं, को क्वांटम ट्यूरिंग मशीनों का उपयोग करके परिभाषित किया गया है।

अन्य प्रकार की समस्याएं

जबकि कंप्यूटर वैज्ञानिकों द्वारा अध्ययन किए गए अधिकांश जटिलता वर्ग निर्णय समस्याओं के समूह हैं, अन्य प्रकार की समस्याओं के संदर्भ में परिभाषित कई जटिलता वर्ग भी हैं। विशेष रूप से, जटिलता वर्ग हैं जिनमें गिनती की समस्या (जटिलता), कार्य की समस्याएं और वादा की समस्याएं सम्मिलित हैं। इन्हें नीचे और अधिक विस्तार से समझाया गया है।

गिनती की समस्याएं

Main article: गिनती की समस्या (जटिलता)

एक गिनती की समस्या न केवल क्या एक समाधान उपस्थित है (जैसा कि एक निर्णय समस्या के साथ) पूछती है, लेकिन पूछती है कि कितने समाधान उपस्थित हैं। उदाहरण के लिए, निर्णय समस्या ${\texttt {CYCLE}}$ पूछता है कि क्या कोई विशेष ग्राफ $G$ एक साधारण चक्र है (जवाब एक साधारण हां/नहीं है); संगत गिनती समस्या $\#{\texttt {CYCLE}}$ (उच्चारण तेज चक्र) कितने सरल चक्र पूछता है $G$ है। गणना समस्या का आउटपुट इस प्रकार एक संख्या है, निर्णय समस्या के आउटपुट के विपरीत, जो एक साधारण हां/नहीं (या स्वीकार/अस्वीकार, 0/1, या अन्य समकक्ष योजना) है।

इस प्रकार, जबकि निर्णय समस्याओं को गणितीय रूप से औपचारिक भाषाओं के रूप में दर्शाया जाता है, गिनती की समस्याओं को गणितीय रूप से फलन (गणित) के रूप में दर्शाया जाता है: एक गिनती समस्या को फलन के रूप में औपचारिक रूप दिया जाता है $f:\{0,1\}^{*}\to \mathbb {N}$ ऐसा है कि हर इनपुट के लिए $w\in \{0,1\}^{*}$, $f(w)$ समाधान की संख्या है। उदाहरण के लिए, में $\#{\texttt {CYCLE}}$ समस्या, इनपुट एक ग्राफ है $G\in \{0,1\}^{*}$ (बिट्स की एक स्ट्रिंग के रूप में दर्शाया गया एक ग्राफ) और $f(G)$ में सरल चक्रों की संख्या है $G$.

गिनती की समस्याएं कई क्षेत्रों में उत्पन्न होती हैं, जिनमें सांख्यिकीय अनुमान, सांख्यिकीय भौतिकी, नेटवर्क डिजाइन और अर्थशास्त्र सम्मिलित हैं।

महत्वपूर्ण जटिलता वर्ग

Main article: ♯पी

1. P(उच्चारण तेज P) गिनती की समस्याओं का एक महत्वपूर्ण वर्ग है जिसे NP के गिनती संस्करण के रूप में माना जा सकता है। NP से संबंध इस तथ्य से उत्पन्न होता है कि किसी समस्या के समाधान की संख्या एक गैर-नियतात्मक ट्यूरिंग मशीन के संगणना वृक्ष में स्वीकार करने वाली शाखाओं की संख्या के बराबर होती है। # P इस प्रकार औपचारिक रूप से निम्नानुसार परिभाषित किया गया है:

#P सभी फलनों का समुच्चय है $f:\{0,1\}^{*}\to \mathbb {N}$ ऐसा है कि एक बहुपद समय गैर नियतात्मक ट्यूरिंग मशीन है $M$ ऐसा कि सभी के लिए $w\in \{0,1\}^{*}$, $f(w)$ में स्वीकार करने वाली शाखाओं की संख्या के बराबर है $M$का संगणना वृक्ष चालू है $w$.

और जिस तरह NP को गैर-निर्धारणवाद के संदर्भ में और एक सत्यापनकर्ता (यानी एक इंटरैक्टिव प्रूफ प्रणाली के रूप में) दोनों के रूप में परिभाषित किया जा सकता है, उसी तरह #P को भी एक सत्यापनकर्ता के संदर्भ में समान रूप से परिभाषित किया जा सकता है। याद रखें कि एक निर्णय समस्या NP में है यदि किसी दिए गए समस्या उदाहरण के लिए बहुपद-समय जांच योग्य प्रमाणपत्र (जटिलता) उपस्थित है- यानी, NP पूछता है कि क्या इनपुट के लिए सदस्यता का प्रमाण (प्रमाणपत्र) उपस्थित है जिसे जांचा जा सकता है बहुपद समय में शुद्धता। कक्षा #P पूछती है कितने ऐसे प्रमाणपत्र उपस्थित हैं। इस संदर्भ में, #P को निम्नानुसार परिभाषित किया गया है:

#P कार्यों का समूह है $f:\{0,1\}^{*}\to \mathbb {N}$ जैसे कि एक बहुपद उपस्थित है $p:\mathbb {N} \to \mathbb {N}$ और एक बहुपद-समय ट्यूरिंग मशीन $V$ (सत्यापनकर्ता), ऐसा है कि हर के लिए $w\in \{0,1\}^{*}$, $f(w)={\Big |}{\big \{}c\in \{0,1\}^{p(|w|)}:V(w,c)=1{\big \}}{\Big |}$. दूसरे शब्दों में, $f(w)$ समुच्चयके आकार के बराबर है जिसमें बहुपद-आकार के सभी प्रमाण पत्र हैं $w$.

कार्य समस्याएं

Main article: फलन की समस्या

गणना की समस्याएं कार्यों की समस्याओं नामक समस्याओं की एक विस्तृत श्रेणी का एक सबसम्मुचय हैं। एक फलन समस्या एक प्रकार की समस्या है जिसमें एक फलन (गणित) के मान $f:A\to B$ गणना की जाती है। औपचारिक रूप से, एक कार्य समस्या $f$ संबंध के रूप में परिभाषित किया गया है $R$ एक मनमाने ढंग से वर्णमाला (औपचारिक भाषाओं) के तार पर $\Sigma$ है

$R\subseteq \Sigma ^{*}\times \Sigma ^{*}$

एक एल्गोरिदम हल करता है $f$ अगर हर इनपुट के लिए $x$ ऐसा है कि वहाँ एक उपस्थित है $y$ संतुष्टि देने वाला $(x,y)\in R$, एल्गोरिथ्म ऐसा एक उत्पन करता है $y$. यह कहने का एक और विधि है $f$ एक फलन (गणित) है और एल्गोरिदम हल करता है $f(x)$ सभी के लिए $x\in \Sigma ^{*}$ है

महत्वपूर्ण जटिलता वर्ग

एक महत्वपूर्ण कार्य जटिलता वर्ग FP(जटिलता) है, जो कुशलता से हल करने योग्य कार्यों का वर्ग है। अधिक विशेष रूप से, FPफलन समस्याओं का समुच्चय है जिसे नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में हल किया जा सकता है। FP को P (जटिलता) के समकक्ष कार्य समस्या के रूप में माना जा सकता है। महत्वपूर्ण रूप से, FP गिनती की समस्याओं और P बनाम NPदोनों में कुछ अंतर्दृष्टि प्रदान करता है। यदि #P = FP, तो NPमें समस्याओं के लिए प्रमाणपत्रों की संख्या निर्धारित करने वाले कार्य कुशलता से हल करने योग्य हैं। और चूँकि प्रमाणपत्रों की संख्या की गणना करना कम से कम उतना ही कठिन है जितना यह निर्धारित करना कि कोई प्रमाण पत्र उपस्थित है, इसका पालन करना चाहिए कि यदि #P=FP तो P=NP (यह ज्ञात नहीं है कि क्या यह उल्टा है, यानी P=NP का तात्पर्य है #P=FP).

जिस तरह FPPके समतुल्य कार्य समस्या है, उसी तरह FNP(जटिलता) NP(जटिलता) के समतुल्य कार्य समस्या है। महत्वपूर्ण रूप से, FP= FNPअगर और केवल अगर P= NP है।

वादा समस्या

Main article: वादा समस्या

वादा समस्याएं निर्णय समस्याओं का एक सामान्यीकरण है जिसमें किसी समस्या के लिए इनपुट की गारंटी (वादा) सभी संभावित इनपुट के एक विशेष उपसमुच्चय से होती है। याद रखें कि एक निर्णय समस्या के साथ $L\subseteq \{0,1\}^{*}$, एक एल्गोरिथ्म $M$ के लिए $L$ प्रत्येक पर (सही ढंग से) कार्य करना चाहिए $w\in \{0,1\}^{*}$. एक वादा समस्या इनपुट आवश्यकता को कम करती है $M$ इनपुट को कुछ सबसम्मुचय तक सीमित करके $\{0,1\}^{*}$.

विशेष रूप से, एक वादा समस्या को गैर-प्रतिच्छेदी सेटों की एक जोड़ी के रूप में परिभाषित किया गया है $(\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})$, जहाँ:

• $\Pi _{\text{ACCEPT}}\subseteq \{0,1\}^{*}$ स्वीकार किए जाने वाले सभी इनपुट का समुच्चय है।
• $\Pi _{\text{REJECT}}\subseteq \{0,1\}^{*}$ अस्वीकार किए गए सभी इनपुट का समुच्चय है।

एक एल्गोरिथ्म के लिए इनपुट $M$ एक वादा समस्या के लिए $(\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})$ इस प्रकार है $\Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}$जिसे वचन कहते हैं। स्ट्रिंग्स इन $\Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}$ वचन पूरा करने वाले कहे जाते हैं। परिभाषा से, $\Pi _{\text{ACCEPT}}$ और $\Pi _{\text{REJECT}}$ असंयुक्त होना चाहिए, अर्थात् $\Pi _{\text{ACCEPT}}\cap \Pi _{\text{REJECT}}=\emptyset$.

इस फॉर्मूलेशन के अन्दर, यह देखा जा सकता है कि निर्णय की समस्याएं मामूली वादे के साथ वादा समस्याओं का सबसम्मुचय हैं $\Pi _{\text{ACCEPT}}\cup \Pi _{\text{REJECT}}=\{0,1\}^{*}$. इस प्रकार निर्णय समस्याओं के साथ केवल समस्या को केवल परिभाषित करना सरल होता है $\Pi _{\text{ACCEPT}}$ (साथ $\Pi _{\text{REJECT}}$ निहित रूप से $\{0,1\}^{*}/\Pi _{\text{ACCEPT}}$), जिसे इस पूरे पृष्ठ में दर्शाया गया है $L$ उस पर जोर देना $\Pi _{\text{ACCEPT}}=L$ एक औपचारिक भाषा है।

वादा समस्याएं कई कम्प्यूटेशनल समस्याओं के अधिक प्राकृतिक सूत्रीकरण के लिए बनाती हैं। उदाहरण के लिए, एक कम्प्यूटेशनल समस्या कुछ इस तरह हो सकती है जैसे कि एक प्लेनर ग्राफ दिया गया हो, निर्धारित करें या नहीं ... इसे अधिकांशतः एक निर्णय समस्या के रूप में कहा जाता है, जिसमें यह माना जाता है कि कुछ अनुवाद स्कीमा है जो प्रत्येक स्ट्रिंग को लेती है $s\in \{0,1\}^{*}$ एक समतलीय ग्राफ के लिए। चुकीं, इसे एक प्रॉमिस समस्या के रूप में परिभाषित करना अधिक सरल है जिसमें इनपुट को प्लानर ग्राफ होने का वादा किया जाता है।

जटिलता वर्गों से संबंध

वादा समस्याएं निर्णय समस्याओं के मानक जटिलता वर्गों के लिए एक वैकल्पिक परिभाषा प्रदान करती हैं। P, उदाहरण के लिए, एक वादा समस्या के रूप में परिभाषित किया जा सकता है:

P वादा समस्याओं का वर्ग है जो नियतात्मक बहुपद समय में हल करने योग्य हैं। यानी वादा समस्या $(\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})$ P में है यदि कोई बहुपद-समय एल्गोरिथम उपस्थित है $M$ ऐसा है कि:

• हर एक के लिए $x\in \Pi _{\text{ACCEPT}},M(x)=1$
• हमेशा के लिए $x\in \Pi _{\text{REJECT}},M(x)=0$

निर्णय समस्याओं के वर्ग-अर्थात, औपचारिक भाषाओं के रूप में परिभाषित समस्याओं के वर्ग-इस प्रकार समस्याओं का वादा करने के लिए स्वाभाविक रूप से अनुवाद करते हैं, जहां एक भाषा $L$ कक्षा में बस है $L=\Pi _{\text{ACCEPT}}$ और $\Pi _{\text{REJECT}}$ निहित है $\{0,1\}^{*}/\Pi _{\text{ACCEPT}}$.

P जैसे कई मूलभूत जटिलता वर्गों को वादा समस्याओं के रूप में तैयार करना उनकी प्रकृति में थोड़ी अतिरिक्त अंतर्दृष्टि प्रदान करता है। चुकीं, कुछ जटिलता वर्ग हैं जिनके लिए उन्हें वादा समस्याओं के रूप में तैयार करना कंप्यूटर वैज्ञानिकों के लिए उपयोगी रहा है। उदाहरण के लिए, प्रॉमिस प्रॉब्लम्स ने SZK (सांख्यिकीय शून्य-ज्ञान) के अध्ययन में महत्वपूर्ण भूमिका निभाई है।

जटिलता वर्गों के बीच संबंधों का सारांश

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

निर्णय समस्या

File:SolidLine.png| कोलस्पैन=2 |

File:SolidLine.png|-शैली= पाठ्य-संरेखण:केंद्र;

प्रकार 0 (पुनरावर्ती गणना योग्य)

अनिर्णनीय

File:SolidLine.png|-शैली= पाठ्य-संरेखण:केंद्र;

डिसाइडेबल

File:SolidLine.png|-शैली= पाठ्य-संरेखण:केंद्र;

EXPSPACE

|-शैली= पाठ्य-संरेखण:केंद्र;

नेक्सपीटाइम

|-शैली= पाठ्य-संरेखण:केंद्र;

EXPTIME

|-शैली= पाठ्य-संरेखण:केंद्र;

PSPACE

File:SolidLine.png| चौड़ाई =40 | File:SolidLine.png

|

|-शैली= पाठ्य-संरेखण:केंद्र;

टाइप 1 (संदर्भ संवेदनशील)

File:SolidLine.png

| सीमा ="1" | |

|-शैली= पाठ्य-संरेखण:केंद्र;

File:SolidLine.png

File:SolidLine.png

|

|-शैली= पाठ्य-संरेखण:केंद्र;

File:SolidLine.png

File:SolidLine.png| co-NP

BQP

NP

File:SolidLine.png

File:SolidLine.png

|

|-शैली= पाठ्य-संरेखण:केंद्र;

File:SolidLine.png

File:SolidLine.png

| बीपीपी

|-शैली= पाठ्य-संरेखण:केंद्र;

File:SolidLine.png

File:SolidLine.png

|

|-शैली= पाठ्य-संरेखण:केंद्र;

File:SolidLine.png

File:SolidLine.png| कोलस्पैन = 5 | P

File:SolidLine.png

File:SolidLine.png

|-शैली= पाठ्य-संरेखण:केंद्र;

File:SolidLine.png| कोलस्पैन=2 | एनसी

File:SolidLine.png| कोलस्पैन =2 | File:SolidLine.png|-शैली= पाठ्य-संरेखण:केंद्र;

टाइप 2 (संदर्भ मुक्त)

File:SolidLine.png|-शैली= पाठ्य-संरेखण:केंद्र;

टाइप 3 (नियमित)

यह भी देखें

• जटिलता वर्गों की सूची

ग्रन्थसूची

• Aaronson, Scott (8 January 2017). "P=?NP". Electronic Colloquim on Computational Complexity. Weizmann Institute of Science. Archived from the original on June 17, 2020.
• Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. Draft. Archived from the original on February 23, 2022. ISBN 978-0-521-42426-4.
• Arora, Sanjeev (Spring 2003). "Complexity classes having to do with counting". Computer Science 522: Computational Complexity Theory. Princeton University. Archived from the original on May 21, 2021. {{cite web}}: |archive-date= / |archive-url= timestamp mismatch (help)
• Barak, Boaz (Spring 2006). "Complexity of counting" (PDF). Computer Science 522: Computational Complexity. Princeton University. Archived from the original on April 3, 2021.
• Fortnow, Lance (1997). "Counting Complexity" (PDF). In Hemaspaandra, Lane A.; Selman, Alan L. (eds.). Complexity Theory Retrospective II. Springer. pp. 81–106. ISBN 9780387949734. Archived from the original (PDF) on June 18, 2022.
• Gasarch, William I. (2019). "Guest Column: The Third P =? NP Poll" (PDF). University of Maryland. Archived (PDF) from the original on November 2, 2021.
• Goldreich, Oded (2006). "On Promise Problems: A Survey" (PDF). In Goldreich, Oded; Rosenberg, Arnold L.; Selman, Alen L. (eds.). Theoretical Computer Science. Lecture Notes in Computer Science, vol 3895 (PDF). Lecture Notes in Computer Science. Vol. 3895. Springer. pp. 254–290. doi:10.1007/11685654_12. ISBN 978-3-540-32881-0. Archived (PDF) from the original on May 6, 2021.
• Lee, James R. (May 22, 2014). "Lecture 16" (PDF). CSE431: Introduction to Theory of Computation. University of Washington. Archived (PDF) from the original on November 29, 2021. Retrieved October 5, 2022.
• Rich, Elaine (2008). Automata, Computability and Complexity: Theory and Applications (PDF). Prentice Hall. ISBN 978-0132288064. Archived (PDF) from the original on January 21, 2022.
• Sipser, Michael (2006). Introduction to the Theory of Computation (PDF) (2nd ed.). USA: Thomson Course Technology. ISBN 0-534-95097-3. Archived from the original (PDF) on February 7, 2022.
• Watrous, John (April 11, 2006). "Lecture 22: Quantum computational complexity" (PDF). University of Waterloo. Archived (PDF) from the original on June 18, 2022.

अग्रिम पठन

• The Complexity Zoo Archived 2019-08-27 at the Wayback Machine: A huge list of complexity classes, a reference for experts.
• Neil Immerman. "Computational Complexity Theory". Archived from the original on 2016-04-16. Includes a diagram showing the hierarchy of complexity classes and how they fit together.
• Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. The standard reference on NP-Complete problems - an important category of problems whose solutions appear to require an impractically long time to compute.