वर्णनात्मक जटिलता सिद्धांत

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

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

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

सेटिंग

जब हम किसी कम्प्यूटेशनल समस्या का वर्णन करने के लिए लॉजिक औपचारिकता का उपयोग करते हैं, तो इनपुट एक सीमित संरचना है, और उस संरचना के तत्व प्रवचन का क्षेत्र हैं। समान्यत: इनपुट या तो एक स्ट्रिंग (बिट्स या वर्णमाला के ऊपर) होता है और तार्किक संरचना के तत्व स्ट्रिंग की स्थिति का प्रतिनिधित्व करते हैं, या इनपुट एक ग्राफ़ होता है और तार्किक संरचना के तत्व इसके शीर्षों का प्रतिनिधित्व करते हैं। इनपुट की लंबाई संबंधित संरचना के आकार से मापी जाएगी। संरचना जो भी हो, हम मान सकते हैं कि ऐसे संबंध हैं जिनका परीक्षण किया जा सकता है, उदाहरण के लिए$E(x,y)$ यह तभी सत्य है जब कोई किनारा हो x को y (संरचना के ग्राफ़ होने की स्थिति में), या$P(n)$ सत्य है यदि और केवल यदि nस्ट्रिंग का वां अक्षर 1 है। ये संबंध प्रथम-क्रम लॉजिक प्रणाली के लिए विधेय हैं। हमारे पास स्थिरांक भी हैं, जो संबंधित संरचना के विशेष तत्व हैं, उदाहरण के लिए यदि हम किसी ग्राफ़ में पहुंच की जांच करना चाहते हैं, तो हमें दो स्थिरांक s (प्रारंभ) और t (टर्मिनल) चुनना होगा।

वर्णनात्मक जटिलता सिद्धांत में हम अधिकांशतः मानते हैं कि तत्वों पर कुल आदेश है और हम तत्वों के बीच समानता की जांच कर सकते हैं। इससे हम तत्वों को संख्याओं के रूप में मान सकते हैं: तत्व x संख्या n का प्रतिनिधित्व करता है यदि और केवल यदि $y<x$ के साथ $(n-1)$ तत्व y हैं। इसके लिए धन्यवाद, हमारे पास आदिम विधेय "बिट" भी हो सकता है, जहां $bit(x,k)$ सत्य है यदि केवल x के द्विआधारी विस्तार का kth बिट 1 है। (हम जोड़ और गुणा को टर्नरी संबंधों द्वारा प्रतिस्थापित कर सकते हैं जैसे कि $plus(x,y,z)$ सत्य है यदि और केवल यदि $x+y=z$ और $times(x,y,z)$ सत्य है यदि और केवल यदि $x*y=z$।

कॉम्प्लेक्सिटी वर्गों की विशेषताओं का अवलोकन

यदि हम खुद को उत्तराधिकारी संबंध और मूलभूत अंकगणितीय विधेय के साथ आदेशित संरचनाओं तक सीमित रखते हैं, तो हमें निम्नलिखित लक्षण मिलते हैं:

• प्रथम-क्रम तर्क वर्ग AC⁰ को परिभाषित करता है, जो कि बंधी हुई गहराई के बहुपद-आकार के सर्किट द्वारा पहचानी जाने वाली भाषाएँ हैं, जो निरंतर समय में समवर्ती यादृच्छिक एक्सेस मशीन द्वारा पहचानी जाने वाली भाषाओं के समान होती हैं।
• सममित या नियतात्मक सकर्मक समापन ऑपरेटरों के साथ संवर्धित प्रथम-क्रम लॉजिक एल (कॉम्प्लेक्सिटी) उत्पन्न करता है, लॉगरिदमिक स्थान में हल करने योग्य समस्याएं है।
• ट्रांजिटिव क्लोजर ऑपरेटर के साथ प्रथम-क्रम लॉजिक एनएल (कॉम्प्लेक्सिटी) उत्पन्न करता है, जो कि गैर-नियतात्मक लघुगणकीय स्थान में हल करने योग्य समस्याएं हैं।
• कम से कम निश्चित बिंदु ऑपरेटर के साथ प्रथम-क्रम लॉजिक पी (कॉम्प्लेक्सिटी) देता है, नियतिवादी बहुपद समय में हल करने योग्य समस्याएं है।
• अस्तित्वगत दूसरे क्रम का लॉजिक एनपी (कॉम्प्लेक्सिटी) उत्पन्न करता है।
• सार्वभौमिक द्वितीय-क्रम लॉजिक (अस्तित्वगत द्वितीय-क्रम परिमाणीकरण को छोड़कर) सह-एनपी उत्पन्न करता है।
• दूसरा-क्रम (कॉम्प्लेक्सिटी) या द्वितीय-क्रम लॉजिक PH (कॉम्प्लेक्सिटी) से मेल खाता है।
• ट्रांजिटिव क्लोजर (कम्यूटेटिव या नहीं) के साथ दूसरे क्रम का लॉजिक पीएसपीएसीई उत्पन्न करता है, जो बहुपद स्थान में हल करने योग्य समस्याएं हैं।
• कम से कम निश्चित बिंदु ऑपरेटर के साथ दूसरे क्रम का लॉजिक EXPTIME देता है, घातीय समय में हल होने वाली समस्याएं।
• HO (कॉम्प्लेक्सिटी), उच्च-क्रम लॉजिक द्वारा परिभाषित कॉम्प्लेक्सिटी वर्ग, प्राथमिक के समान है

उप-बहुपद समय

बिना किसी ऑपरेटर के एफओ

सर्किट कॉम्प्लेक्सिटी में, इच्छित विधेय के साथ प्रथम-क्रम लॉजिक को AC⁰ के समान दिखाया जा सकता है जो AC पदानुक्रम में प्रथम श्रेणी है। इसलिए एफओ के प्रतीकों से सर्किट के नोड्स में एक प्राकृतिक अनुवाद होता है जिसमें $\forall ,\exists$ प्राणी $\land$ और $\lor$ आकार का n.उपस्थित होता है। अंकगणितीय विधेय के साथ हस्ताक्षर में प्रथम-क्रम लॉजिक AC⁰ के प्रतिबंध को दर्शाता है एलएच (कॉम्प्लेक्सिटी) में निर्माण योग्य सर्किटों का वर्ग । केवल ऑर्डर संबंध वाले हस्ताक्षर में प्रथम-क्रम लॉजिक स्टार-मुक्त लैंग्वेज के सेट से मेल खाता है।

सकर्मक समापन लॉजिक

प्रथम-क्रम लॉजिक को अभिव्यंजक शक्ति में अधिक लाभ मिलता है जब इसे एक ऑपरेटर के साथ बढ़ाया जाता है जो बाइनरी संबंध के सकर्मक समापन की गणना करता है। परिणामी सकर्मक समापन लॉजिक को आदेशित संरचनाओं पर एनएल (कॉम्प्लेक्सिटी) या गैर-नियतात्मक लघुगणक स्थान (एनएल) को चिह्नित करने के लिए जाना जाता है। इसका उपयोग नील इमरमैन द्वारा यह दिखाने के लिए किया गया था कि NL पूरक के तहत संवर्त है (अथार्त NL = co-NL)।

ट्रांज़िटिव क्लोजर ऑपरेटर को फिक्स्ड-पॉइंट लॉजिक या नियतात्मक ट्रांजिटिव क्लोजर लॉजिक तक सीमित करते समय, परिणामी लॉजिक ऑर्डर किए गए संरचनाओं पर एल (कॉम्प्लेक्सिटी) को स्पष्ट रूप से चित्रित करता है।

दूसरे क्रम के क्रॉम सूत्र

उन संरचनाओं पर जिनमें उत्तराधिकारी कार्य होता है, एनएल को दूसरे क्रम के क्रॉम सूत्र द्वारा भी चित्रित किया जा सकता है।

एसओ-क्रोम, संयोजक सामान्य रूप में दूसरे क्रम के सूत्रों के साथ परिभाषित बूलियन प्रश्नों का सेट है, जैसे कि पहले क्रम के क्वांटिफायर सार्वभौमिक होते हैं और सूत्र का क्वांटिफायर-मुक्त भाग क्रोम सूत्र में होता है, जिसका अर्थ है कि पहले क्रम का सूत्र विच्छेदन का एक संयोजन है, और प्रत्येक विच्छेदन में अधिकतम दो वेरिएबल होते हैं। प्रत्येक दूसरे क्रम का क्रॉम सूत्र अस्तित्वगत दूसरे क्रम के क्रॉम सूत्र के समान है।

एसओ-क्रोम एक उत्तराधिकारी फ़ंक्शन के साथ संरचनाओं पर एनएल की विशेषता बताता है।

बहुपद समय

आदेशित संरचनाओं पर, प्रथम-क्रम न्यूनतम निश्चित-बिंदु तर्क PTIME को कैप्चर करता है:

प्रथम-क्रम न्यूनतम निश्चित-बिंदु लॉजिक

एफओ [एलएफपी] कम से कम निश्चित-बिंदु ऑपरेटर द्वारा प्रथम-क्रम लॉजिक का विस्तार है, जो एक मोनोटोन अभिव्यक्ति के निश्चित-बिंदु को व्यक्त करता है। यह पुनरावृत्ति को व्यक्त करने की क्षमता के साथ प्रथम-क्रम लॉजिक को बढ़ाता है। नील इमरमैन और मोशे वर्डी द्वारा स्वतंत्र रूप से दिखाए गए इमरमैन-वर्दी प्रमेय से पता चलता है कि एफओ [एलएफपी] आदेशित संरचनाओं पर PTIME की विशेषता बताता है।

2022 तक, यह अभी भी खुला है कि क्या अव्यवस्थित संरचनाओं पर PTIME की विशेषता बताने वाला कोई प्राकृतिक लॉजिक है।

एबितबौल-वियानू प्रमेय बताता है कि सभी संरचनाओं पर FO[LFP]=FO[PFP] यदि और केवल यदि FO[LFP]=FO[PFP]; इसलिए यदि और केवल यदि P=PSPACE इस परिणाम को अन्य फिक्सपॉइंट्स तक बढ़ा दिया गया है।

दूसरे क्रम के हॉर्न सूत्र

उत्तराधिकारी फ़ंक्शन की उपस्थिति में, PTIME को दूसरे क्रम के हॉर्न सूत्रों द्वारा भी चित्रित किया जा सकता है।

एसओ-हॉर्न एसओ सूत्रों के साथ डिजंक्टिव सामान्य रूप में परिभाषित बूलियन प्रश्नों का सेट है, जैसे कि प्रथम-क्रम क्वांटिफायर सभी सार्वभौमिक हैं और फॉर्मूला का क्वांटिफायर-मुक्त हिस्सा हॉर्न उपवाक्य फॉर्म में है, जिसका अर्थ है कि यह एक बड़ा और है OR का, और प्रत्येक OR में संभवतः एक को छोड़कर प्रत्येक वेरिएबल को अस्वीकार दिया गया है।

यह वर्ग उत्तराधिकारी फ़ंक्शन वाली संरचनाओं पर पी (कॉम्प्लेक्सिटी) के समान है। उन सूत्रों को अस्तित्वगत दूसरे क्रम के हॉर्न लॉजिक में प्रीनेक्स सूत्रों में बदला जा सकता है।

गैर-नियतात्मक बहुपद समय

फागिन का प्रमेय

रोनाल्ड फागिन का 1974 का प्रमाण कि कॉम्प्लेक्सिटी वर्ग एनपी को अस्तित्वगत दूसरे क्रम के लॉजिक में स्वयंसिद्ध संरचनाओं के उन वर्गों द्वारा स्पष्ट रूप से चित्रित किया गया था, जो डिस्क्रिप्टिव कॉम्प्लेक्सिटी थ्योरी का प्रारंभिक बिंदु था।

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

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

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

एनपी से परे

आंशिक निश्चित बिंदु PSPACE है

बहुपद स्थान, पीएसपीएसीई में गणना योग्य सभी समस्याओं के वर्ग को अधिक अभिव्यंजक आंशिक निश्चित-बिंदु ऑपरेटर के साथ प्रथम-क्रम लॉजिक को बढ़ाकर चित्रित किया जा सकता है।

आंशिक निश्चित-बिंदु लॉजिक , एफओ [पीएफपी], आंशिक निश्चित-बिंदु ऑपरेटर के साथ प्रथम-क्रम लॉजिक का विस्तार है, जो एक सूत्र के निश्चित-बिंदु को व्यक्त करता है यदि कोई है और अन्यथा 'गलत' लौटाता है।

आंशिक निश्चित-बिंदु लॉजिक आदेशित संरचनाओं पर PSPACE की विशेषता बताता है।

सकर्मक समापन PSPACE है

दूसरे-क्रम के लॉजिक को पहले-क्रम के लॉजिक की तरह ही एक ट्रांजिटिव क्लोजर ऑपरेटर द्वारा बढ़ाया जा सकता है, जिसके परिणामस्वरूप SO[TC] होता है। टीसी ऑपरेटर अब लॉजिक के रूप में दूसरे क्रम के वेरिएबल भी ले सकता है। SO[TC] PSPACE की विशेषता बताता है। चूंकि ऑर्डर को दूसरे क्रम के लॉजिक में संदर्भित किया जा सकता है, इसलिए यह लक्षण वर्णन ऑर्डर की गई संरचनाओं को नहीं मानता है।

प्राथमिक कार्य

प्रारंभिक कार्यों के समय कॉम्प्लेक्सिटी वर्ग एलिमेंटरी को एचओ द्वारा चित्रित किया जा सकता है, संरचनाओं की कॉम्प्लेक्सिटी वर्ग जिसे उच्च-क्रम लॉजिक के सूत्रों द्वारा पहचाना जा सकता है। उच्च-क्रम तर्क, उच्च-क्रम परिमाणकों के साथ प्रथम-क्रम तर्क और द्वितीय-क्रम तर्क का विस्तार है। $i$th क्रम और गैर-नियतात्मक एल्गोरिदम के बीच एक संबंध है जिसका समय घातांक के $i-1$ स्तर से घिरा है।

परिभाषा

हम उच्च-क्रम वाले चर परिभाषित करते हैं। क्रम $i>1$ के एक चर में एक एरीटी $k$ है और क्रम $i-1$के तत्वों के $k$-टुपल्स के किसी भी सेट का प्रतिनिधित्व करता है। वे समान्यत: बड़े अक्षरों में लिखे जाते हैं और क्रम को निरुपित करने के लिए घातांक के रूप में एक प्राकृतिक संख्या के साथ लिखे जाते हैं। उच्च-क्रम तर्क प्रथम-क्रम सूत्रों का सेट है जहां हम उच्च-क्रम चर पर मात्रा का ठहराव जोड़ते हैं; इसलिए हम एफओ लेख में परिभाषित शब्दों को दोबारा परिभाषित किए बिना उनका उपयोग करेंगे।

HO$^{i}$ अधिiम $i$ क्रम के चर वाले सूत्रों का समूह है। HO$_{j}^{i}$ फॉर्म के सूत्रों का सबसेट है $\phi =\exists {\overline {X_{1}^{i}}}\forall {\overline {X_{2}^{i}}}\dots Q{\overline {X_{j}^{i}}}\psi$ जहां $Q$ एक क्वांटिफायर है और $Q{\overline {X^{i}}}$ का मतलब है कि ${\overline {X^{i}}}$ समान क्वांटिफिकेशन के साथ ऑर्डर i के वेरिएबल का एक टुपल है। तो HO$_{j}^{i}$ क्रम $i$ के क्वांटिफायर के $j$ विकल्पों के साथ सूत्रों का सेट है, जो $\exists$ से शुरू होता है, उसके बाद क्रम $i-1$ का एक सूत्र होता है।

टेट्रेशन के मानक नोटेशन का उपयोग करते हुए, $\exp _{2}^{0}(x)=x$ और $\exp _{2}^{i+1}(x)=2^{\exp _{2}^{i}(x)}$. $\exp _{2}^{i+1}(x)=2^{2^{2^{2^{\dots ^{2^{x}}}}}}$ साथ $i$ गुना $2$ है

सामान्य रूप

ऑर्डर $i$वां का प्रत्येक सूत्र प्रीनेक्स सामान्य रूप में एक सूत्र के समान है, जहां हम $i$वां ऑर्डर के चर पर मात्रा का ठहराव लिखते हैं और फिर सामान्य रूप में $i-1$ का एक सूत्र लिखते हैं।

कॉम्प्लेक्सिटी वर्गों से संबंध

एचओ प्राथमिक कार्यों के वर्ग एलिमेंटरी के समान है। अधिक स्पष्ट होने के लिए, ${\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))$, जिसका अर्थ है $(i-2)$2s का एक टावर, जो $n^{c}$ पर समाप्त होता है, जहां $c$ एक स्थिरांक है। इसका एक विशेष मामला यह है कि $\exists {\mathsf {SO}}={\mathsf {HO}}_{0}^{2}={\mathsf {NTIME}}(n^{O(1)})={\color {Blue}{\mathsf {NP}}}$, जो बिल्कुल फेगिन का प्रमेय है। बहुपद पदानुक्रम में ओरेकल मशीनों का उपयोग करना ${\mathsf {HO}}_{j}^{i}={\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)})^{\Sigma _{j}^{\mathsf {P}}})$ है .

संदर्भ

• Immerman, Neil (1999). Descriptive complexity. Springer. ISBN 0-387-98600-6. OCLC 901297152.

बाहरी संबंध

• Neil Immerman's descriptive complexity page, including a diagram