Structural complexity theory
कंप्यूटर विज्ञान के कम्प्यूटेशनल जटिलता सिद्धांत में, संरचनात्मक जटिलता सिद्धांत या बस संरचनात्मक जटिलता व्यक्तिगत समस्याओं और एल्गोरिदम की कम्प्यूटेशनल जटिलता के बजाय जटिलता वर्गों का अध्ययन है। इसमें विभिन्न जटिलता वर्गों की आंतरिक संरचनाओं और विभिन्न जटिलता वर्गों के बीच संबंधों दोनों का शोध शामिल है। यह सिद्धांत इस तरह के पहले और अभी भी सबसे महत्वपूर्ण प्रश्न, पी = एन. पी. समस्या को हल करने के प्रयासों (अभी भी विफल) के परिणामस्वरूप उभरा है। अधिकांश शोध इस धारणा के आधार पर किया जाता है कि पी एन. पी. के बराबर नहीं है और एक अधिक दूरगामी अनुमान है कि जटिलता वर्गों का बहुपद समय पदानुक्रम अनंत है। महत्वपूर्ण परिणाम संपीड़न प्रमेय संपीड़न प्रमेय संगणनीय कार्यों की जटिलता के बारे में एक महत्वपूर्ण प्रमेय है। प्रमेय में कहा गया है कि कम्प्यूटेबल सीमा के साथ कोई सबसे बड़ा जटिलता वर्ग मौजूद नहीं है, जिसमें सभी कम्प्यूटेबल कार्य शामिल हैं। अंतरिक्ष पदानुक्रम प्रमेय अंतरिक्ष पदानुक्रम प्रमेय पृथक्करण परिणाम हैं जो दर्शाते हैं कि नियतात्मक और गैर-नियतात्मक दोनों मशीनें कुछ शर्तों के अधीन अधिक स्थान (स्पर्शोन्मुख रूप से) में अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, एक नियतात्मक ट्यूरिंग मशीन अंतरिक्ष एन की तुलना में अंतरिक्ष एन लॉग एन में अधिक निर्णय समस्याओं को हल कर सकती है। समय के लिए कुछ कमजोर अनुरूप प्रमेय समय पदानुक्रम प्रमेय हैं। समय पदानुक्रम प्रमेय समय पदानुक्रम प्रमेय ट्यूरिंग मशीनों पर समय-सीमित गणना के बारे में महत्वपूर्ण कथन हैं। अनौपचारिक रूप से, इन प्रमेयों का कहना है कि अधिक समय दिए जाने पर, एक ट्यूरिंग मशीन अधिक समस्याओं को हल कर सकती है। उदाहरण के लिए, ऐसी समस्याएं हैं जिन्हें n2 समय के साथ हल किया जा सकता है लेकिन n समय के साथ नहीं। वीरता-वजीरानी प्रमेय वीरता-वजीरानी प्रमेय कम्प्यूटेशनल जटिलता सिद्धांत में एक प्रमेय है। यह लेस्ली वैलियंट और विजय वजीरानी द्वारा अपने पेपर एन. पी. में साबित किया गया था जो 1986 में प्रकाशित अद्वितीय समाधानों का पता लगाने जितना आसान है। प्रमेय में कहा गया है कि यदि असंदिग्ध-एसएटी के लिए एक बहुपद समय एल्गोरिथ्म है, तो एनपी = आरपी। सबूत मुलमुली-वजीरानी अलगाव लेम्मा पर आधारित है, जिसका उपयोग बाद में सैद्धांतिक कंप्यूटर विज्ञान में कई महत्वपूर्ण अनुप्रयोगों के लिए किया गया था। सिप्सर-लॉटमैन प्रमेय सिप्सर-लॉटमैन प्रमेय या सिप्सर-गैक्स-लॉटमैन प्रमेय बताता है कि बाउंडेड-एरर प्रोबेबिलिस्टिक पॉलीनॉमियल (बी. पी. पी.) समय, बहुपद समय पदानुक्रम में निहित है, और विशेष रूप से σ2 θ Π2। 1970 में वाल्टर सेविच द्वारा सिद्ध किए गए सेविच के प्रमेय से निर्धारक और गैर-निर्धारक अंतरिक्ष जटिलता के बीच संबंध मिलता है। इसमें कहा गया है कि किसी भी कार्य के लिए, टोडा की प्रमेय टोडा की प्रमेय एक परिणाम है जिसे सिनोसुके टोडा ने अपने शोध पत्र "पीपी इज अस हार्ड एज द पोलीनोमिअल-टाइम हायरार्की" (1991) में साबित किया था और इसे 1998 का गोडेल पुरस्कार दिया गया था। प्रमेय में कहा गया है कि संपूर्ण बहुपद पदानुक्रम पी. एच. पी. पी. पी. में निहित है; इसका तात्पर्य एक निकट संबंधित कथन से है, कि पी. एच. P#P में निहित है। इमर्मन-ज़ेलेप्सेनी प्रमेय इमर्मन-ज़ेलेप्सेनी प्रमेय को 1987 में नील इमर्मन और रॉबर्ट ज़ेलेप्सेनी द्वारा स्वतंत्र रूप से साबित किया गया था, जिसके लिए उन्होंने 1995 का गोडेल पुरस्कार साझा किया था। अपने सामान्य रूप में प्रमेय बताती है कि किसी भी फलन के लिए एन. एस. पी. ए. सी. ई. (एस. (एन.)) = सह-एन. एस. पी. ए. सी. ई. (एस. (एन.)) एस. (एन.) लॉग. एन. के लिए। परिणाम एन. एल. = सह-एन. एल. के रूप में समतुल्य है; हालाँकि यह विशेष मामला है जब एस. (एन.) = लॉग. एन., यह एक मानक पैडिंग तर्क द्वारा सामान्य प्रमेय का तात्पर्य है। परिणाम ने दूसरी एल. बी. ए. समस्या को हल कर दिया। शोध विषय इस क्षेत्र में अनुसंधान की प्रमुख दिशाओं में शामिल हैंः जटिलता वर्गों के बारे में विभिन्न अनसुलझी समस्याओं से उपजे प्रभावों का अध्ययन विभिन्न प्रकार के संसाधन-प्रतिबंधित कटौती का अध्ययन और विभिन्न प्रतिबंधों के परिणामों और भंडारण और डेटा तक पहुंच के तंत्र का संबंधित पूर्ण भाषा अध्ययन।