जटिलता वर्ग

File:Complexity subsets pspace.svg

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

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

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

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

पृष्ठभूमि

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

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

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

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

File:Decision Problem.svg

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

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

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

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

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

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

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

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

Main article: Turing machine

Error creating thumbnail:

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

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

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

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

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

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

Main article: Nondeterministic Turing machine

File:Difference between deterministic and Nondeterministic.svg

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

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

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

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

संसाधन सीमा

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

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

समय सीमा

Main article: Time complexity

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

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

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

Main article: Space complexity

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

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

See also: List of complexity classes

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

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

• समय जटिलता वर्ग ${\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))$ अंतरिक्ष nondeterministic ट्यूरिंग मशीन।

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

Main article: Time complexity

पी और एनपी

Main articles: P (complexity) and NP (complexity)

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

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

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

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

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

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

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

पी बनाम एनपी समस्या

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

EXPTIME और NEXPTIME

Main articles: EXPTIME and NEXPTIME

EXPTIME (कभी-कभी EXP के रूप में संक्षिप्त) निर्णयात्मक समस्याओं का वर्ग है जिसे घातीय समय में नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है और NEXPTIME (कभी-कभी 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 का सख्त सुपरसेट है और NEXPTIME NP का सख्त सुपरसेट है। आगे यह मामला है कि EXPTIME$\subseteq$अगला। यह ज्ञात नहीं है कि यह उचित है या नहीं, लेकिन यदि P = NP तो EXPTIME को NEXPTIME के ​​बराबर होना चाहिए।

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

Main article: Space complexity

एल और एनएल ===

Main articles: L (complexity) and NL (complexity)

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

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

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

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

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

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

Main article: PSPACE (complexity)

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

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

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

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

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

Main article: EXPSPACE

जटिलता वर्ग EXPSPACE और NEXPSPACE, EXPTIME और NEXPTIME के ​​स्पेस अनुरूप हैं। यही है, 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 का सख्त सुपरसेट है।

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

क्लोजर

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

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

क्लोजर गुण प्रमुख कारणों में से एक हैं क्योंकि कई जटिलता वर्गों को उनके रूप में परिभाषित किया गया है। उदाहरण के लिए, एक ऐसी समस्या को लीजिए, जिसका हल निकाला जा सकता है $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})$). चूंकि हम अभी भी कुशल माने जाने के लिए एक अन्य कुशल एल्गोरिथ्म के साथ एक कुशल एल्गोरिथ्म की रचना करना चाहते हैं, बहुपद सबसे छोटा वर्ग है जो कुशल एल्गोरिदम की संरचना सुनिश्चित करता है। (ध्यान दें कि पी की परिभाषा भी उपयोगी है क्योंकि अनुभवजन्य रूप से, पी में लगभग सभी समस्याएं जो व्यावहारिक रूप से उपयोगी हैं, वास्तव में निम्न क्रम बहुपद रनटाइम हैं, और पी के बाहर लगभग सभी समस्याएं जो व्यावहारिक रूप से उपयोगी हैं, उनके पास कोई ज्ञात एल्गोरिदम नहीं है छोटे घातीय रनटाइम के साथ, यानी with $O(c^{n})$ रनटाइम कहाँ $c$ 1 के करीब है।)

कटौती

See also: Reduction (complexity)

कमी की अवधारणा का उपयोग करके कई जटिलता वर्गों को परिभाषित किया गया है। एक कमी एक समस्या का दूसरी समस्या में रूपांतरण है, यानी कमी एक समस्या से इनपुट लेती है और उन्हें दूसरी समस्या के इनपुट में बदल देती है। उदाहरण के लिए, आप साधारण आधार-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$. इस प्रकार सी में कोई समस्या कठिन नहीं है $X$, क्योंकि एक एल्गोरिथ्म के लिए $X$ हमें सी में किसी भी समस्या को हल करने की अनुमति देता है जिसमें अधिकांश बहुपद मंदी होती है। विशेष रूप से, एनपी के लिए कठिन समस्याओं के सेट को एनपी कठिन समस्याओं का सेट कहा जाता है।

संपूर्णता

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

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

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

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

Main article: Savitch's theorem

सैविच की प्रमेय नियतात्मक और गैर-नियतात्मक अंतरिक्ष संसाधनों के बीच संबंध स्थापित करती है। यह दर्शाता है कि यदि एक गैर-नियतात्मक ट्यूरिंग मशीन किसी समस्या का समाधान कर सकती है $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: Time hierarchy theorem and Space hierarchy theorem

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 में समाहित है।

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

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

• संभाव्य ट्यूरिंग मशीनों का उपयोग करके कई वर्गों को परिभाषित किया गया है, जिसमें कक्षाएं बाउंड-त्रुटि संभाव्य बहुपद, पीपी (जटिलता), आरपी (जटिलता), और जेडपीपी (जटिलता) शामिल हैं।
• आईपी (जटिलता), एमए (जटिलता), और एएम (जटिलता) सहित इंटरएक्टिव प्रूफ सिस्टम का उपयोग करके कई वर्गों को परिभाषित किया गया है।
• बूलियन सर्किट का उपयोग करके कई वर्गों को परिभाषित किया गया है, जिसमें वर्ग पी/पॉली और इसके उपवर्ग एनसी (जटिलता) और एसी (जटिलता) शामिल हैं।
• बीक्यूपी और क्यूएमए कक्षाओं सहित क्वांटम ट्यूरिंग मशीनों का उपयोग करके कई वर्गों को परिभाषित किया गया है

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

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

Main article: Randomized computation

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

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

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

File:Randomized Complexity Classes.svg

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

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

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

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

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

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

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

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

इंटरएक्टिव प्रूफ सिस्टम

Main article: Interactive proof system

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

File:Interactive proof (complexity).svg

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

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

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

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

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

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

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

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

Main article: Circuit complexity

File:Three input Boolean circuit.jpg

बूलियन फ़ंक्शन की गणना करने वाले बूलियन सर्किट का उदाहरण $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$ गेट नहीं नहीं हैं।

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

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

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

क्वांटम गणना

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

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

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

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

Main article: Counting problem (complexity)

एक गिनती की समस्या न केवल क्या एक समाधान मौजूद है (जैसा कि एक निर्णय समस्या के साथ) पूछती है, लेकिन पूछती है कि कितने समाधान मौजूद हैं। उदाहरण के लिए, निर्णय समस्या ${\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: ♯P

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

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

और जिस तरह एनपी को गैर-निर्धारणवाद के संदर्भ में और एक सत्यापनकर्ता (यानी एक इंटरैक्टिव प्रूफ सिस्टम के रूप में) दोनों के रूप में परिभाषित किया जा सकता है, उसी तरह #P को भी एक सत्यापनकर्ता के संदर्भ में समान रूप से परिभाषित किया जा सकता है। याद रखें कि एक निर्णय समस्या एनपी में है यदि किसी दिए गए समस्या उदाहरण के लिए बहुपद-समय जांच योग्य प्रमाणपत्र (जटिलता) मौजूद है- यानी, एनपी पूछता है कि क्या इनपुट के लिए सदस्यता का प्रमाण (प्रमाणपत्र) मौजूद है जिसे जांचा जा सकता है बहुपद समय में शुद्धता। कक्षा #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: Function problem

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

जिस तरह एफपी पी के समतुल्य कार्य समस्या है, उसी तरह एफएनपी (जटिलता) एनपी (जटिलता) के समतुल्य कार्य समस्या है। महत्वपूर्ण रूप से, एफपी = एफएनपी अगर और केवल अगर पी = एनपी।

वादा समस्या

Main article: Promise problem

वादा समस्याएं निर्णय समस्याओं का एक सामान्यीकरण है जिसमें किसी समस्या के लिए इनपुट की गारंटी (वादा) सभी संभावित इनपुट के एक विशेष उपसमुच्चय से होती है। याद रखें कि एक निर्णय समस्या के साथ $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 वादा समस्याओं का वर्ग है जो नियतात्मक बहुपद समय में हल करने योग्य हैं। यानी वादा समस्या $(\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}}$.

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

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

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

Decision Problem

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

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

Type 0 (Recursively enumerable)

Undecidable

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

Decidable

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

EXPSPACE

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

NEXPTIME

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

EXPTIME

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

PSPACE

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

File:DottedLine.png

File:DottedLine.png|

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

Type 1 (Context Sensitive)

File:SolidLine.png

File:DottedLine.png| सीमा ="1" | File:DottedLine.png|

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

File:SolidLine.png

File:SolidLine.png

File:DottedLine.png

File:DottedLine.png|

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

File:SolidLine.png

File:SolidLine.png| co-NP

BQP

NP

File:SolidLine.png

File:SolidLine.png

File:DottedLine.png

File:DottedLine.png|

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

File:SolidLine.png

File:SolidLine.png

File:DottedLine.png| BPP

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

File:SolidLine.png

File:SolidLine.png

File:DottedLine.png

File:DottedLine.png|

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

File:SolidLine.png

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

File:SolidLine.png

File:SolidLine.png

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

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

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

Type 2 (Context Free)

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

Type 3 (Regular)

यह भी देखें

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

ग्रन्थसूची

• 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.