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

Revision as of 16:08, 25 July 2023

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

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

डिस्क्रिप्टिव कॉम्प्लेक्सिटी का पहला मुख्य परिणाम फागिन का प्रमेय था, जिसे 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⁰ को परिभाषित करता है, जो कि बंधी हुई गहराई के बहुपद-आकार के सर्किट द्वारा पहचानी जाने वाली भाषाएँ हैं, जो निरंतर समय में समवर्ती यादृच्छिक एक्सेस मशीन द्वारा पहचानी जाने वाली भाषाओं के समान होती हैं।^[1]
सममित या नियतात्मक सकर्मक समापन ऑपरेटरों के साथ संवर्धित प्रथम-क्रम लॉजिक एल (कॉम्प्लेक्सिटी) उत्पन्न करता है, लॉगरिदमिक स्थान में हल करने योग्य समस्याएं है।^[2]
ट्रांजिटिव क्लोजर ऑपरेटर के साथ प्रथम-क्रम लॉजिक एनएल (कॉम्प्लेक्सिटी) उत्पन्न करता है, जो कि गैर-नियतात्मक लघुगणकीय स्थान में हल करने योग्य समस्याएं हैं।^[3]
कम से कम निश्चित बिंदु ऑपरेटर के साथ प्रथम-क्रम लॉजिक पी (कॉम्प्लेक्सिटी) देता है, नियतिवादी बहुपद समय में हल करने योग्य समस्याएं है।^[3]
अस्तित्वगत दूसरे क्रम का लॉजिक एनपी (कॉम्प्लेक्सिटी) उत्पन्न करता है।^[3]
सार्वभौमिक द्वितीय-क्रम लॉजिक (अस्तित्वगत द्वितीय-क्रम परिमाणीकरण को छोड़कर) सह-एनपी उत्पन्न करता है।^[4]
दूसरा-क्रम (कॉम्प्लेक्सिटी) या द्वितीय-क्रम लॉजिक PH (कॉम्प्लेक्सिटी) से मेल खाता है।^[3]
ट्रांजिटिव क्लोजर (कम्यूटेटिव या नहीं) के साथ दूसरे क्रम का लॉजिक पीएसपीएसीई उत्पन्न करता है, जो बहुपद स्थान में हल करने योग्य समस्याएं हैं। ^[5]
कम से कम निश्चित बिंदु ऑपरेटर के साथ दूसरे क्रम का लॉजिक EXPTIME देता है, घातीय समय में हल होने वाली समस्याएं।^[6]
HO (कॉम्प्लेक्सिटी), उच्च-क्रम लॉजिक द्वारा परिभाषित कॉम्प्लेक्सिटी वर्ग, प्राथमिक के समान है^[7]

उप-बहुपद समय

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

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

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

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

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

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

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

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

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

बहुपद समय

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

एनपी से परे

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

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

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

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

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

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

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

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

परिभाषा

हम उच्च-क्रम वाले चर परिभाषित करते हैं। क्रम $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 1999, p. 86
↑ Grädel, Erich; Schalthöfer, Svenja (2019). विकल्पहीन लघुगणकीय स्थान. Leibniz International Proceedings in Informatics (LIPIcs) (in English). Vol. 138. pp. 31:1–31:15. doi:10.4230/LIPICS.MFCS.2019.31. ISBN 9783959771177.
↑ ^3.0 ^3.1 ^3.2 ^3.3 Immerman 1999, p. 242
↑ ^4.0 ^4.1 ^4.2 Fagin, Ron (1974). "Generalized first-order spectra and polynomial-time recognizable sets". In Karp, Richard (ed.). संगणना की जटिलता. pp. 43–73.
↑ Immerman 1999, p. 243
↑ Abiteboul, Serge; Vardi, Moshe Y.; Vianu, Victor (1997-01-15). "फिक्सपॉइंट लॉजिक्स, रिलेशनल मशीनें और कम्प्यूटेशनल जटिलता". Journal of the ACM (in English). 44 (1): 30–56. doi:10.1145/256292.256295. ISSN 0004-5411. S2CID 11338470.
↑ Hella, Lauri; Turull-Torres, José María (2006). "उच्च-क्रम तर्कों के साथ प्रश्नों की गणना करना". Theoretical Computer Science. Essex, UK: Elsevier Science Publishers Ltd. 355 (2): 197–214. doi:10.1016/j.tcs.2006.01.009. ISSN 0304-3975.
↑ Immerman 1999, p. 86
↑ Robert., McNaughton (1971). काउंटर-फ्री ऑटोमेटा. M.I.T. Press. ISBN 0-262-13076-9. OCLC 651199926.
↑ Immerman 1999, p. 22
↑ Immerman, Neil (1988). "गैर-नियतात्मक स्थान कार्यान्वयन के तहत बंद है". SIAM Journal on Computing. 17 (5): 935–938. doi:10.1137/0217058. ISSN 0097-5397.
↑ ^12.0 ^12.1 Immerman 1999, p. 153–4
↑ Immerman, Neil (1986). "बहुपद समय में गणना योग्य संबंधपरक प्रश्न". Information and Control (in English). 68 (1–3): 86–104. doi:10.1016/s0019-9958(86)80029-8.
↑ Vardi, Moshe Y. (1982). "The Complexity of Relational Query Languages (Extended Abstract)". Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82. pp. 137–146. CiteSeerX 10.1.1.331.6045. doi:10.1145/800070.802186. ISBN 978-0897910705. S2CID 7869248. {{cite book}}: |journal= ignored (help)
↑ Serge Abiteboul, Moshe Y. Vardi, Victor Vianu: Fixpoint logics, relational machines, and computational complexity Journal of the ACM archive, Volume 44 , Issue 1 (January 1997), Pages: 30-56, ISSN 0004-5411
↑ Grädel, Erich (1992-07-13). "दूसरे क्रम के तर्क के टुकड़ों द्वारा जटिलता वर्गों को कैप्चर करना". Theoretical Computer Science (in English). 101 (1): 35–57. doi:10.1016/0304-3975(92)90149-A. ISSN 0304-3975.
↑ Immerman 1999, p. 115
↑ Immerman 1999, p. 121
↑ Immerman 1999, p. 181
↑ Abiteboul, S.; Vianu, V. (1989). "प्रथम-क्रम तर्क और डेटालॉग-जैसी भाषाओं के फिक्सपॉइंट एक्सटेंशन". [1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science. IEEE Comput. Soc. Press: 71–79. doi:10.1109/lics.1989.39160. ISBN 0-8186-1954-6. S2CID 206437693.
↑ Harel, D.; Peleg, D. (1984-01-01). "स्थिर तर्क, गतिशील तर्क और जटिलता वर्गों पर". Information and Control (in English). 60 (1): 86–102. doi:10.1016/S0019-9958(84)80023-6. ISSN 0019-9958.
↑ Hella, Lauri; Turull-Torres, José María (2006). "उच्च-क्रम तर्कों के साथ प्रश्नों की गणना करना". Theoretical Computer Science. Essex, UK: Elsevier Science Publishers Ltd. 355 (2): 197–214. doi:10.1016/j.tcs.2006.01.009. ISSN 0304-3975.

संदर्भ

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

बाहरी संबंध

Neil Immerman's descriptive complexity page, including a diagram

[1] Immerman 1999, p. 86

[2] Grädel, Erich; Schalthöfer, Svenja (2019). विकल्पहीन लघुगणकीय स्थान. Leibniz International Proceedings in Informatics (LIPIcs) (in English). Vol. 138. pp. 31:1–31:15. doi:10.4230/LIPICS.MFCS.2019.31. ISBN 9783959771177.

[:0-3] 3.0 ^3.1 ^3.2 ^3.3 Immerman 1999, p. 242

[:1-4] 4.0 ^4.1 ^4.2 Fagin, Ron (1974). "Generalized first-order spectra and polynomial-time recognizable sets". In Karp, Richard (ed.). संगणना की जटिलता. pp. 43–73.

[5] Immerman 1999, p. 243

[6] Abiteboul, Serge; Vardi, Moshe Y.; Vianu, Victor (1997-01-15). "फिक्सपॉइंट लॉजिक्स, रिलेशनल मशीनें और कम्प्यूटेशनल जटिलता". Journal of the ACM (in English). 44 (1): 30–56. doi:10.1145/256292.256295. ISSN 0004-5411. S2CID 11338470.

[7] Hella, Lauri; Turull-Torres, José María (2006). "उच्च-क्रम तर्कों के साथ प्रश्नों की गणना करना". Theoretical Computer Science. Essex, UK: Elsevier Science Publishers Ltd. 355 (2): 197–214. doi:10.1016/j.tcs.2006.01.009. ISSN 0304-3975.

[8] Immerman 1999, p. 86

[9] Robert., McNaughton (1971). काउंटर-फ्री ऑटोमेटा. M.I.T. Press. ISBN 0-262-13076-9. OCLC 651199926.

[10] Immerman 1999, p. 22

[11] Immerman, Neil (1988). "गैर-नियतात्मक स्थान कार्यान्वयन के तहत बंद है". SIAM Journal on Computing. 17 (5): 935–938. doi:10.1137/0217058. ISSN 0097-5397.

[:2-12] 12.0 ^12.1 Immerman 1999, p. 153–4

[13] Immerman, Neil (1986). "बहुपद समय में गणना योग्य संबंधपरक प्रश्न". Information and Control (in English). 68 (1–3): 86–104. doi:10.1016/s0019-9958(86)80029-8.

[14] Vardi, Moshe Y. (1982). "The Complexity of Relational Query Languages (Extended Abstract)". Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82. pp. 137–146. CiteSeerX 10.1.1.331.6045. doi:10.1145/800070.802186. ISBN 978-0897910705. S2CID 7869248. {{cite book}}: |journal= ignored (help)

[avv-15] Serge Abiteboul, Moshe Y. Vardi, Victor Vianu: Fixpoint logics, relational machines, and computational complexity Journal of the ACM archive, Volume 44 , Issue 1 (January 1997), Pages: 30-56, ISSN 0004-5411

[16] Grädel, Erich (1992-07-13). "दूसरे क्रम के तर्क के टुकड़ों द्वारा जटिलता वर्गों को कैप्चर करना". Theoretical Computer Science (in English). 101 (1): 35–57. doi:10.1016/0304-3975(92)90149-A. ISSN 0304-3975.

[17] Immerman 1999, p. 115

[18] Immerman 1999, p. 121

[19] Immerman 1999, p. 181

[20] Abiteboul, S.; Vianu, V. (1989). "प्रथम-क्रम तर्क और डेटालॉग-जैसी भाषाओं के फिक्सपॉइंट एक्सटेंशन". [1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science. IEEE Comput. Soc. Press: 71–79. doi:10.1109/lics.1989.39160. ISBN 0-8186-1954-6. S2CID 206437693.

[21] Harel, D.; Peleg, D. (1984-01-01). "स्थिर तर्क, गतिशील तर्क और जटिलता वर्गों पर". Information and Control (in English). 60 (1): 86–102. doi:10.1016/S0019-9958(84)80023-6. ISSN 0019-9958.

[22] Hella, Lauri; Turull-Torres, José María (2006). "उच्च-क्रम तर्कों के साथ प्रश्नों की गणना करना". Theoretical Computer Science. Essex, UK: Elsevier Science Publishers Ltd. 355 (2): 197–214. doi:10.1016/j.tcs.2006.01.009. ISSN 0304-3975.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

@@ Line 1: / Line 1: @@
 {{Short description|Branch of mathematical logic}}
-वर्णनात्मक जटिलता [[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[परिमित मॉडल सिद्धांत]] की एक शाखा है जो [[औपचारिक भाषा]]ओं को व्यक्त करने के लिए आवश्यक [[तर्क]] के प्रकार के आधार पर [[जटिलता वर्ग]]ों की विशेषता बताती है। उदाहरण के लिए, [[पीएच (जटिलता)]], बहुपद पदानुक्रम में सभी जटिलता वर्गों का संघ, ठीक दूसरे क्रम के तर्क के बयानों द्वारा व्यक्त की जाने वाली भाषाओं का वर्ग है। जटिलता और परिमित संरचनाओं के तर्क के बीच यह संबंध परिणामों को एक क्षेत्र से दूसरे क्षेत्र में आसानी से स्थानांतरित करने की अनुमति देता है, नए प्रमाण तरीकों की सुविधा प्रदान करता है और अतिरिक्त सबूत प्रदान करता है कि मुख्य जटिलता वर्ग किसी तरह प्राकृतिक हैं और परिभाषित करने के लिए उपयोग की जाने वाली विशिष्ट [[अमूर्त मशीन]]ों से बंधे नहीं हैं। उन्हें।
+डिस्क्रिप्टिव  कॉम्प्लेक्सिटी [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी]]  और [[परिमित मॉडल सिद्धांत|परिमित मॉडल थ्योरी]]  की एक शाखा है जो [[औपचारिक भाषा|औपचारिक]] लैंग्वेज  को व्यक्त करने के लिए आवश्यक [[तर्क|लॉजिक]]  के प्रकार के आधार पर [[जटिलता वर्ग|कॉम्प्लेक्सिटी वर्ग]] की विशेषता बताती है। उदाहरण के लिए, [[पीएच (जटिलता)|पीएच (कॉम्प्लेक्सिटी)]], बहुपद पदानुक्रम में सभी कॉम्प्लेक्सिटी वर्गों का संघ, ठीक दूसरे क्रम के लॉजिक  के कथनों  द्वारा व्यक्त की जाने वाली लैंग्वेज  का वर्ग है। कॉम्प्लेक्सिटी और परिमित संरचनाओं के लॉजिक  के बीच यह संबंध परिणामों को एक क्षेत्र से दूसरे क्षेत्र में सरलता से स्थानांतरित करने की अनुमति देता है, नए प्रमाण विधि की सुविधा प्रदान करता है और अतिरिक्त प्रमाण प्रदान करता है कि मुख्य कॉम्प्लेक्सिटी वर्ग किसी तरह प्राकृतिक हैं और परिभाषित करने के लिए उपयोग की जाने वाली विशिष्ट [[अमूर्त मशीन]] से बंधे नहीं हैं।
-विशेष रूप से, प्रत्येक [[तार्किक प्रणाली]] इसमें व्यक्त होने योग्य [[क्वेरी (जटिलता)]] का एक [[सबसेट]] तैयार करती है। प्रश्न - जब परिमित संरचनाओं तक सीमित होते हैं - पारंपरिक जटिलता सिद्धांत की [[कम्प्यूटेशनल समस्या]]ओं के अनुरूप होते हैं।
+विशेष रूप से, प्रत्येक [[तार्किक प्रणाली]] इसमें व्यक्त होने योग्य [[क्वेरी (जटिलता)|क्वेरी (कॉम्प्लेक्सिटी)]] का एक [[सबसेट]] तैयार करती है। प्रश्न - जब परिमित संरचनाओं तक सीमित होते हैं - पारंपरिक कॉम्प्लेक्सिटी थ्योरी  की [[कम्प्यूटेशनल समस्या]]ओं के अनुरूप होते हैं।
-वर्णनात्मक जटिलता का पहला मुख्य परिणाम फागिन का प्रमेय था, जिसे 1974 में [[रोनाल्ड फागिन]] द्वारा दिखाया गया था। इसने स्थापित किया कि [[एनपी (जटिलता)]] वास्तव में अस्तित्वगत दूसरे क्रम के तर्क के वाक्यों द्वारा व्यक्त की जाने वाली भाषाओं का समूह है; अर्थात्, [[संबंध (गणित)]]एस, [[फ़ंक्शन (गणित)]]एस, और उपसमुच्चय पर [[सार्वभौमिक परिमाणीकरण]] को छोड़कर [[दूसरे क्रम का तर्क]]। बाद में कई अन्य वर्गों को भी इसी तरह चित्रित किया गया।
+डिस्क्रिप्टिव कॉम्प्लेक्सिटी का पहला मुख्य परिणाम फागिन का प्रमेय था, जिसे 1974 में [[रोनाल्ड फागिन]] द्वारा दिखाया गया था। इसने स्थापित किया कि [[एनपी (जटिलता)|एनपी (कॉम्प्लेक्सिटी)]] वास्तव में अस्तित्वगत दूसरे क्रम के लॉजिक  के वाक्यों द्वारा व्यक्त की जाने वाली लैंग्वेज  का समूह है; अर्थात्, [[संबंध (गणित)]]एस, [[फ़ंक्शन (गणित)]]एस, और उपसमुच्चय पर [[सार्वभौमिक परिमाणीकरण]] को छोड़कर [[दूसरे क्रम का तर्क|दूसरे क्रम का लॉजिक]]  बाद में कई अन्य वर्गों को भी इसी तरह चित्रित किया गया था।
 ==सेटिंग==
-जब हम किसी कम्प्यूटेशनल समस्या का वर्णन करने के लिए तर्क औपचारिकता का उपयोग करते हैं, तो इनपुट एक सीमित संरचना है, और उस संरचना के तत्व [[प्रवचन का क्षेत्र]] हैं। आम तौर पर इनपुट या तो एक स्ट्रिंग (बिट्स या वर्णमाला के ऊपर) होता है और तार्किक संरचना के तत्व स्ट्रिंग की स्थिति का प्रतिनिधित्व करते हैं, या इनपुट एक ग्राफ़ होता है और तार्किक संरचना के तत्व इसके शीर्षों का प्रतिनिधित्व करते हैं। इनपुट की लंबाई संबंधित संरचना के आकार से मापी जाएगी।
+जब हम किसी कम्प्यूटेशनल समस्या का वर्णन करने के लिए लॉजिक  औपचारिकता का उपयोग करते हैं, तो इनपुट एक सीमित संरचना है, और उस संरचना के तत्व [[प्रवचन का क्षेत्र]] हैं। समान्यत: इनपुट या तो एक स्ट्रिंग (बिट्स या वर्णमाला के ऊपर) होता है और तार्किक संरचना के तत्व स्ट्रिंग की स्थिति का प्रतिनिधित्व करते हैं, या इनपुट एक ग्राफ़ होता है और तार्किक संरचना के तत्व इसके शीर्षों का प्रतिनिधित्व करते हैं। इनपुट की लंबाई संबंधित संरचना के आकार से मापी जाएगी। संरचना जो भी हो, हम मान सकते हैं कि ऐसे संबंध हैं जिनका परीक्षण किया जा सकता है, उदाहरण के लिए<math>E(x,y)</math> यह तभी सत्य है जब कोई किनारा हो {{mvar|x}} को {{mvar|y}} (संरचना के ग्राफ़ होने की स्थिति में), या<math>P(n)</math> सत्य है यदि और केवल यदि {{mvar|n}}स्ट्रिंग का वां अक्षर 1 है। ये संबंध प्रथम-क्रम लॉजिक  प्रणाली के लिए विधेय हैं। हमारे पास स्थिरांक भी हैं, जो संबंधित संरचना के विशेष तत्व हैं, उदाहरण के लिए यदि हम किसी ग्राफ़ में पहुंच की जांच करना चाहते हैं, तो हमें दो स्थिरांक s (प्रारंभ) और t (टर्मिनल) चुनना होगा।
-संरचना जो भी हो, हम मान सकते हैं कि ऐसे संबंध हैं जिनका परीक्षण किया जा सकता है, उदाहरण के लिए<math>E(x,y)</math> यह तभी सत्य है जब कोई किनारा हो {{mvar|x}} को {{mvar|y}} (संरचना के ग्राफ़ होने की स्थिति में), या<math>P(n)</math> सत्य है यदि और केवल यदि {{mvar|n}}स्ट्रिंग का वां अक्षर 1 है। ये संबंध प्रथम-क्रम तर्क प्रणाली के लिए विधेय हैं। हमारे पास स्थिरांक भी हैं, जो संबंधित संरचना के विशेष तत्व हैं, उदाहरण के लिए यदि हम किसी ग्राफ़ में पहुंच की जांच करना चाहते हैं, तो हमें दो स्थिरांक s (प्रारंभ) और t (टर्मिनल) चुनना होगा।
-वर्णनात्मक जटिलता सिद्धांत में हम अक्सर मानते हैं कि तत्वों पर कुल आदेश है और हम तत्वों के बीच समानता की जांच कर सकते हैं। इससे हम तत्वों को संख्याओं के रूप में मान सकते हैं: तत्व {{mvar|x}} संख्या का प्रतिनिधित्व करता है {{mvar|n}} यदि और केवल यदि हैं <math>(n-1)</math> तत्वों {{mvar|y}} साथ <math>y<x</math>. इसके लिए धन्यवाद, हमारे पास आदिम विधेय बिट भी हो सकता है, जहां <math>bit(x,k)</math> सत्य है यदि केवल {{mvar|k}}के बाइनरी विस्तार का वां बिट {{mvar|x}} 1 है। (हम जोड़ और गुणा को त्रिक संबंधों से प्रतिस्थापित कर सकते हैं जैसे कि <math>plus(x,y,z)</math> सत्य है यदि और केवल यदि <math>x+y=z</math> और <math>times(x,y,z)</math> सत्य है यदि और केवल यदि <math>x*y=z</math>).
+वर्णनात्मक जटिलता सिद्धांत में हम  अधिकांशतः मानते हैं कि तत्वों पर कुल आदेश है और हम तत्वों के बीच समानता की जांच कर सकते हैं। इससे हम तत्वों को संख्याओं के रूप में मान सकते हैं: तत्व {{mvar|x}} संख्या {{mvar|n}} का प्रतिनिधित्व करता है यदि और केवल यदि <math>y<x</math> के साथ <math>(n-1)</math> तत्व y हैं। इसके लिए धन्यवाद, हमारे पास आदिम विधेय "बिट" भी हो सकता है, जहां <math>bit(x,k)</math> सत्य है यदि केवल x के द्विआधारी विस्तार का kth बिट 1 है। (हम जोड़ और गुणा को टर्नरी संबंधों द्वारा प्रतिस्थापित कर सकते हैं जैसे कि <math>plus(x,y,z)</math> सत्य है यदि और केवल यदि <math>x+y=z</math> और <math>times(x,y,z)</math> सत्य है यदि और केवल यदि <math>x*y=z</math>।
-==जटिलता वर्गों की विशेषताओं का अवलोकन==
+==कॉम्प्लेक्सिटी वर्गों की विशेषताओं का अवलोकन==
-यदि हम खुद को उत्तराधिकारी संबंध और बुनियादी अंकगणितीय विधेय के साथ आदेशित संरचनाओं तक सीमित रखते हैं, तो हमें निम्नलिखित लक्षण मिलते हैं:
+यदि हम खुद को उत्तराधिकारी संबंध और मूलभूत अंकगणितीय विधेय के साथ आदेशित संरचनाओं तक सीमित रखते हैं, तो हमें निम्नलिखित लक्षण मिलते हैं:
-* [[प्रथम-क्रम तर्क]] वर्ग AC0|AC को परिभाषित करता है<sup>0</sup>, बंधी हुई गहराई के बहुपद-आकार सर्किट द्वारा पहचानी जाने वाली भाषाएँ, जो निरंतर समय में समवर्ती यादृच्छिक एक्सेस मशीन द्वारा पहचानी जाने वाली भाषाओं के बराबर होती हैं।<ref>Immerman 1999, p. 86</ref>
+*प्रथम-क्रम तर्क वर्ग AC<sup>0</sup> को परिभाषित करता है, जो कि बंधी हुई गहराई के बहुपद-आकार के सर्किट द्वारा पहचानी जाने वाली भाषाएँ हैं, जो निरंतर समय में समवर्ती यादृच्छिक एक्सेस मशीन द्वारा पहचानी जाने वाली भाषाओं के समान  होती हैं।<ref>Immerman 1999, p. 86</ref>
-* सममित या नियतात्मक [[ सकर्मक समापन ]] ऑपरेटरों के साथ संवर्धित प्रथम-क्रम तर्क [[एल (जटिलता)]] उत्पन्न करता है, लॉगरिदमिक स्थान में हल करने योग्य समस्याएं।<ref>{{Cite book|last1=Grädel|first1=Erich|last2=Schalthöfer|first2=Svenja|date=2019|title=विकल्पहीन लघुगणकीय स्थान|series=Leibniz International Proceedings in Informatics (LIPIcs)|volume=138|url=http://drops.dagstuhl.de/opus/volltexte/2019/10975/|language=en|pages=31:1–31:15|doi=10.4230/LIPICS.MFCS.2019.31|isbn=9783959771177}}</ref>
+* सममित या नियतात्मक [[ सकर्मक समापन ]] ऑपरेटरों के साथ संवर्धित प्रथम-क्रम लॉजिक  [[एल (जटिलता)|एल (कॉम्प्लेक्सिटी)]] उत्पन्न करता है, लॉगरिदमिक स्थान में हल करने योग्य समस्याएं है।<ref>{{Cite book|last1=Grädel|first1=Erich|last2=Schalthöfer|first2=Svenja|date=2019|title=विकल्पहीन लघुगणकीय स्थान|series=Leibniz International Proceedings in Informatics (LIPIcs)|volume=138|url=http://drops.dagstuhl.de/opus/volltexte/2019/10975/|language=en|pages=31:1–31:15|doi=10.4230/LIPICS.MFCS.2019.31|isbn=9783959771177}}</ref>
-* ट्रांजिटिव क्लोजर ऑपरेटर के साथ प्रथम-क्रम तर्क [[एनएल (जटिलता)]] उत्पन्न करता है, जो कि गैर-नियतात्मक लघुगणकीय स्थान में हल करने योग्य समस्याएं हैं।<ref name=":0">Immerman 1999, p. 242</ref>
+* ट्रांजिटिव क्लोजर ऑपरेटर के साथ प्रथम-क्रम लॉजिक  [[एनएल (जटिलता)|एनएल (कॉम्प्लेक्सिटी)]] उत्पन्न करता है, जो कि गैर-नियतात्मक लघुगणकीय स्थान में हल करने योग्य समस्याएं हैं।<ref name=":0">Immerman 1999, p. 242</ref>
-* कम से कम निश्चित बिंदु ऑपरेटर के साथ प्रथम-क्रम तर्क [[पी (जटिलता)]] देता है, नियतिवादी बहुपद समय में हल करने योग्य समस्याएं।<ref name=":0" />* अस्तित्वगत दूसरे क्रम का तर्क एनपी (जटिलता) उत्पन्न करता है।<ref name=":0" />* सार्वभौमिक द्वितीय-क्रम तर्क (अस्तित्वगत द्वितीय-क्रम परिमाणीकरण को छोड़कर) [[सह-एनपी]] उत्पन्न करता है।<ref name=":1">{{Cite book|last=Fagin|first=Ron|title=संगणना की जटिलता|year=1974|editor-last=Karp|editor-first=Richard|pages=43{{mdash}}73|chapter=Generalized first-order spectra and polynomial-time recognizable sets}}</ref>
+* कम से कम निश्चित बिंदु ऑपरेटर के साथ प्रथम-क्रम लॉजिक  [[पी (जटिलता)|पी (कॉम्प्लेक्सिटी)]] देता है, नियतिवादी बहुपद समय में हल करने योग्य समस्याएं है।<ref name=":0" />
-* SO (जटिलता)|द्वितीय-क्रम तर्क PH (जटिलता) से मेल खाता है।<ref name=":0" />* ट्रांजिटिव क्लोजर (कम्यूटेटिव या नहीं) के साथ दूसरे क्रम का तर्क पीएसपीएसीई उत्पन्न करता है, जो बहुपद स्थान में हल करने योग्य समस्याएं हैं। <ref>Immerman 1999, p. 243</ref>
+*अस्तित्वगत दूसरे क्रम का लॉजिक  एनपी (कॉम्प्लेक्सिटी) उत्पन्न करता है।<ref name=":0" />
-* कम से कम निश्चित बिंदु ऑपरेटर के साथ दूसरे क्रम का तर्क [[EXPTIME]] देता है, घातीय समय में हल होने वाली समस्याएं।<ref>{{Cite journal|last1=Abiteboul|first1=Serge|last2=Vardi|first2=Moshe Y.|last3=Vianu|first3=Victor|date=1997-01-15|title=फिक्सपॉइंट लॉजिक्स, रिलेशनल मशीनें और कम्प्यूटेशनल जटिलता|url=https://dl.acm.org/doi/10.1145/256292.256295|journal=[[Journal of the ACM]]|language=en|volume=44|issue=1|pages=30–56|doi=10.1145/256292.256295|s2cid=11338470|issn=0004-5411}}</ref> * HO (जटिलता), [[उच्च-क्रम तर्क]] द्वारा परिभाषित जटिलता वर्ग, [[प्राथमिक]] के बराबर है<ref>{{Cite journal| first1 = Lauri|last1= Hella|first2 = José María|last2 = Turull-Torres | title =उच्च-क्रम तर्कों के साथ प्रश्नों की गणना करना| journal =[[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 355 | issue = 2 | year = 2006 | pages = 197–214   | issn =0304-3975 | publisher =Elsevier Science Publishers Ltd. | place =  Essex, UK | url = http://portal.acm.org/citation.cfm?id=1142890.1142897 | doi=10.1016/j.tcs.2006.01.009| doi-access = free }}</ref>
+*सार्वभौमिक द्वितीय-क्रम लॉजिक  (अस्तित्वगत द्वितीय-क्रम परिमाणीकरण को छोड़कर) [[सह-एनपी]] उत्पन्न करता है।<ref name=":1">{{Cite book|last=Fagin|first=Ron|title=संगणना की जटिलता|year=1974|editor-last=Karp|editor-first=Richard|pages=43{{mdash}}73|chapter=Generalized first-order spectra and polynomial-time recognizable sets}}</ref>
+* दूसरा-क्रम  (कॉम्प्लेक्सिटी) या द्वितीय-क्रम लॉजिक  PH (कॉम्प्लेक्सिटी) से मेल खाता है।<ref name=":0" />
+*ट्रांजिटिव क्लोजर (कम्यूटेटिव या नहीं) के साथ दूसरे क्रम का लॉजिक  पीएसपीएसीई उत्पन्न करता है, जो बहुपद स्थान में हल करने योग्य समस्याएं हैं। <ref>Immerman 1999, p. 243</ref>
+* कम से कम निश्चित बिंदु ऑपरेटर के साथ दूसरे क्रम का लॉजिक  [[EXPTIME]] देता है, घातीय समय में हल होने वाली समस्याएं।<ref>{{Cite journal|last1=Abiteboul|first1=Serge|last2=Vardi|first2=Moshe Y.|last3=Vianu|first3=Victor|date=1997-01-15|title=फिक्सपॉइंट लॉजिक्स, रिलेशनल मशीनें और कम्प्यूटेशनल जटिलता|url=https://dl.acm.org/doi/10.1145/256292.256295|journal=[[Journal of the ACM]]|language=en|volume=44|issue=1|pages=30–56|doi=10.1145/256292.256295|s2cid=11338470|issn=0004-5411}}</ref>
+*HO (कॉम्प्लेक्सिटी), [[उच्च-क्रम तर्क|उच्च-क्रम लॉजिक]]  द्वारा परिभाषित कॉम्प्लेक्सिटी वर्ग, [[प्राथमिक]] के समान  है<ref>{{Cite journal| first1 = Lauri|last1= Hella|first2 = José María|last2 = Turull-Torres | title =उच्च-क्रम तर्कों के साथ प्रश्नों की गणना करना| journal =[[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 355 | issue = 2 | year = 2006 | pages = 197–214   | issn =0304-3975 | publisher =Elsevier Science Publishers Ltd. | place =  Essex, UK | url = http://portal.acm.org/citation.cfm?id=1142890.1142897 | doi=10.1016/j.tcs.2006.01.009| doi-access = free }}</ref>
@@ Line 28: / Line 31: @@
 === बिना किसी ऑपरेटर के एफओ ===
-[[सर्किट जटिलता]] में, मनमाना विधेय के साथ प्रथम-क्रम तर्क को AC0|AC के बराबर दिखाया जा सकता है<sup>0</sup>, [[एसी (जटिलता)]] पदानुक्रम में प्रथम श्रेणी। दरअसल, एफओ के प्रतीकों से सर्किट के नोड्स में एक प्राकृतिक अनुवाद होता है <math>\forall, \exists</math> प्राणी <math>\land</math> और <math>\lor</math> आकार का {{mvar|n}}. अंकगणितीय विधेय के साथ हस्ताक्षर में प्रथम-क्रम तर्क एसी के प्रतिबंध को दर्शाता है<sup>0</sup>[[एलएच (जटिलता)]] में निर्माण योग्य सर्किटों का परिवार।<ref>Immerman 1999, p. 86</ref> केवल ऑर्डर संबंध वाले हस्ताक्षर में प्रथम-क्रम तर्क स्टार-मुक्त भाषाओं के सेट से मेल खाता है।<ref>{{Cite book|last=Robert.|first=McNaughton|url=http://worldcat.org/oclc/651199926|title=काउंटर-फ्री ऑटोमेटा|date=1971|publisher=M.I.T. Press|isbn=0-262-13076-9|oclc=651199926}}</ref><ref>Immerman 1999, p. 22</ref>
+[[सर्किट जटिलता|सर्किट]] कॉम्प्लेक्सिटी में, इच्छित विधेय के साथ प्रथम-क्रम लॉजिक  को  AC<sup>0</sup> के समान  दिखाया जा सकता है जो AC पदानुक्रम में प्रथम श्रेणी है। इसलिए  एफओ के प्रतीकों से सर्किट के नोड्स में एक प्राकृतिक अनुवाद होता है जिसमें <math>\forall, \exists</math> प्राणी <math>\land</math> और <math>\lor</math> आकार का {{mvar|n}}.उपस्थित होता है। अंकगणितीय विधेय के साथ हस्ताक्षर में प्रथम-क्रम लॉजिक  AC<sup>0</sup> के प्रतिबंध को दर्शाता है [[एलएच (जटिलता)|एलएच (कॉम्प्लेक्सिटी)]] में निर्माण योग्य सर्किटों का वर्ग ।<ref>Immerman 1999, p. 86</ref> केवल ऑर्डर संबंध वाले हस्ताक्षर में प्रथम-क्रम लॉजिक  स्टार-मुक्त लैंग्वेज  के सेट से मेल खाता है।<ref>{{Cite book|last=Robert.|first=McNaughton|url=http://worldcat.org/oclc/651199926|title=काउंटर-फ्री ऑटोमेटा|date=1971|publisher=M.I.T. Press|isbn=0-262-13076-9|oclc=651199926}}</ref><ref>Immerman 1999, p. 22</ref>
+=== [[सकर्मक समापन तर्क|सकर्मक समापन लॉजिक]] ===
+प्रथम-क्रम लॉजिक  को अभिव्यंजक शक्ति में अधिक लाभ मिलता है जब इसे एक ऑपरेटर के साथ बढ़ाया जाता है जो बाइनरी संबंध के सकर्मक समापन की गणना करता है। परिणामी सकर्मक समापन लॉजिक  को आदेशित संरचनाओं पर एनएल (कॉम्प्लेक्सिटी)  या  गैर-नियतात्मक लघुगणक स्थान (एनएल) को चिह्नित करने के लिए जाना जाता है। इसका उपयोग [[नील इमरमैन]] द्वारा यह दिखाने के लिए किया गया था कि एनएल पूरक के तहत बंद है (अथार्त NL = co-NL)।<ref>{{Cite journal|last=Immerman|first=Neil|date=1988|title=गैर-नियतात्मक स्थान कार्यान्वयन के तहत बंद है|url=http://dx.doi.org/10.1137/0217058|journal=[[SIAM Journal on Computing]]|volume=17|issue=5|pages=935–938|doi=10.1137/0217058|issn=0097-5397}}</ref>
+ट्रांज़िटिव क्लोजर ऑपरेटर को फिक्स्ड-पॉइंट लॉजिक या नियतात्मक ट्रांजिटिव क्लोजर लॉजिक तक सीमित करते समय, परिणामी लॉजिक  ऑर्डर किए गए संरचनाओं पर एल (कॉम्प्लेक्सिटी) को स्पष्ट रूप से चित्रित करता है।
-=== [[सकर्मक समापन तर्क]] ===
-प्रथम-क्रम तर्क को अभिव्यंजक शक्ति में काफी लाभ मिलता है जब इसे एक ऑपरेटर के साथ बढ़ाया जाता है जो बाइनरी संबंध के सकर्मक समापन की गणना करता है। परिणामी सकर्मक समापन तर्क को आदेशित संरचनाओं पर एनएल (जटिलता) | गैर-नियतात्मक लघुगणक स्थान (एनएल) को चिह्नित करने के लिए जाना जाता है। इसका उपयोग [[नील इमरमैन]] द्वारा यह दिखाने के लिए किया गया था कि एनएल पूरक के तहत बंद है (यानी एनएल = सह-एनएल)।<ref>{{Cite journal|last=Immerman|first=Neil|date=1988|title=गैर-नियतात्मक स्थान कार्यान्वयन के तहत बंद है|url=http://dx.doi.org/10.1137/0217058|journal=[[SIAM Journal on Computing]]|volume=17|issue=5|pages=935–938|doi=10.1137/0217058|issn=0097-5397}}</ref>
-ट्रांज़िटिव क्लोजर ऑपरेटर को फिक्स्ड-पॉइंट लॉजिक # नियतात्मक ट्रांजिटिव क्लोजर लॉजिक तक सीमित करते समय, परिणामी तर्क ऑर्डर किए गए संरचनाओं पर एल (जटिलता) को सटीक रूप से चित्रित करता है।
 === दूसरे क्रम के क्रॉम सूत्र ===
 उन संरचनाओं पर जिनमें उत्तराधिकारी कार्य होता है, एनएल को दूसरे क्रम के क्रॉम सूत्र द्वारा भी चित्रित किया जा सकता है।
-एसओ-क्रोम, [[संयोजक सामान्य रूप]] में दूसरे क्रम के सूत्रों के साथ परिभाषित बूलियन प्रश्नों का सेट है, जैसे कि पहले क्रम के क्वांटिफायर सार्वभौमिक होते हैं और सूत्र का क्वांटिफायर-मुक्त भाग [[क्रोम सूत्र]] में होता है, जिसका अर्थ है कि पहले क्रम का सूत्र विच्छेदन का एक संयोजन है, और प्रत्येक विच्छेदन में अधिकतम दो चर होते हैं। प्रत्येक दूसरे क्रम का क्रॉम सूत्र अस्तित्वगत दूसरे क्रम के क्रॉम सूत्र के बराबर है।
+एसओ-क्रोम, [[संयोजक सामान्य रूप]] में दूसरे क्रम के सूत्रों के साथ परिभाषित बूलियन प्रश्नों का सेट है, जैसे कि पहले क्रम के क्वांटिफायर सार्वभौमिक होते हैं और सूत्र का क्वांटिफायर-मुक्त भाग [[क्रोम सूत्र]] में होता है, जिसका अर्थ है कि पहले क्रम का सूत्र विच्छेदन का एक संयोजन है, और प्रत्येक विच्छेदन में अधिकतम दो वेरिएबल होते हैं। प्रत्येक दूसरे क्रम का क्रॉम सूत्र अस्तित्वगत दूसरे क्रम के क्रॉम सूत्र के समान  है।
 एसओ-क्रोम एक उत्तराधिकारी फ़ंक्शन के साथ संरचनाओं पर एनएल की विशेषता बताता है।<ref name=":2">Immerman 1999, p. 153{{Ndash}}4</ref>
@@ Line 46: / Line 48: @@
 आदेशित संरचनाओं पर, प्रथम-क्रम न्यूनतम निश्चित-बिंदु तर्क PTIME को कैप्चर करता है:
-=== प्रथम-क्रम न्यूनतम निश्चित-बिंदु तर्क ===
+=== प्रथम-क्रम न्यूनतम निश्चित-बिंदु लॉजिक ===
-एफओ[एलएफपी] कम से कम निश्चित-बिंदु ऑपरेटर द्वारा प्रथम-क्रम तर्क का विस्तार है, जो एक मोनोटोन अभिव्यक्ति के निश्चित-बिंदु को व्यक्त करता है। यह पुनरावृत्ति को व्यक्त करने की क्षमता के साथ प्रथम-क्रम तर्क को बढ़ाता है। नील इमरमैन और [[मोशे वर्डी]] द्वारा स्वतंत्र रूप से दिखाए गए इमरमैन-वर्दी प्रमेय से पता चलता है कि एफओ [एलएफपी] आदेशित संरचनाओं पर PTIME की विशेषता बताता है।<ref>{{Cite journal|last=Immerman|first=Neil|year=1986|title=बहुपद समय में गणना योग्य संबंधपरक प्रश्न|journal=[[Information and Control]]|language=en|volume=68|issue=1–3|pages=86–104|doi=10.1016/s0019-9958(86)80029-8|doi-access=free}}</ref><ref>{{Cite book|last=Vardi|first=Moshe Y.|title=Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82|chapter=The Complexity of Relational Query Languages (Extended Abstract)|date=1982|journal=Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing|publisher=ACM|isbn=978-0897910705|series=STOC '82|location=New York, NY, USA|pages=137–146|citeseerx=10.1.1.331.6045|doi=10.1145/800070.802186|s2cid=7869248}}</ref>
+एफओ [एलएफपी] कम से कम निश्चित-बिंदु ऑपरेटर द्वारा प्रथम-क्रम लॉजिक  का विस्तार है, जो एक मोनोटोन अभिव्यक्ति के निश्चित-बिंदु को व्यक्त करता है। यह पुनरावृत्ति को व्यक्त करने की क्षमता के साथ प्रथम-क्रम लॉजिक  को बढ़ाता है। नील इमरमैन और [[मोशे वर्डी]] द्वारा स्वतंत्र रूप से दिखाए गए इमरमैन-वर्दी प्रमेय से पता चलता है कि एफओ [एलएफपी] आदेशित संरचनाओं पर PTIME की विशेषता बताता है।<ref>{{Cite journal|last=Immerman|first=Neil|year=1986|title=बहुपद समय में गणना योग्य संबंधपरक प्रश्न|journal=[[Information and Control]]|language=en|volume=68|issue=1–3|pages=86–104|doi=10.1016/s0019-9958(86)80029-8|doi-access=free}}</ref><ref>{{Cite book|last=Vardi|first=Moshe Y.|title=Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82|chapter=The Complexity of Relational Query Languages (Extended Abstract)|date=1982|journal=Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing|publisher=ACM|isbn=978-0897910705|series=STOC '82|location=New York, NY, USA|pages=137–146|citeseerx=10.1.1.331.6045|doi=10.1145/800070.802186|s2cid=7869248}}</ref>
-तक, यह अभी भी खुला है कि क्या अव्यवस्थित संरचनाओं पर PTIME की विशेषता बताने वाला कोई प्राकृतिक तर्क है।
+तक, यह अभी भी खुला है कि क्या अव्यवस्थित संरचनाओं पर PTIME की विशेषता बताने वाला कोई प्राकृतिक लॉजिक  है।
 एबितबौल-वियानू प्रमेय बताता है कि सभी संरचनाओं पर FO[LFP]=FO[PFP] यदि और केवल यदि FO[LFP]=FO[PFP]; इसलिए यदि और केवल यदि P=PSPACE। इस परिणाम को अन्य फिक्सपॉइंट्स तक बढ़ा दिया गया है।<ref name="avv">Serge Abiteboul, [[Moshe Y. Vardi]], [[Victor Vianu]]: [http://portal.acm.org/citation.cfm?id=256295 Fixpoint logics, relational machines, and computational complexity] Journal of the ACM archive, Volume 44 ,  Issue 1  (January 1997), Pages: 30-56, {{ISSN|0004-5411}}</ref>
@@ Line 54: / Line 57: @@
 === दूसरे क्रम के हॉर्न सूत्र ===
-उत्तराधिकारी फ़ंक्शन की उपस्थिति में, PTIME को दूसरे क्रम के हॉर्न फ़ार्मुलों द्वारा भी चित्रित किया जा सकता है।
+उत्तराधिकारी फ़ंक्शन की उपस्थिति में, PTIME को दूसरे क्रम के हॉर्न सूत्रों द्वारा भी चित्रित किया जा सकता है।
-एसओ-हॉर्न एसओ फ़ार्मुलों के साथ डिजंक्टिव सामान्य रूप में परिभाषित बूलियन प्रश्नों का सेट है, जैसे कि प्रथम-क्रम क्वांटिफायर सभी सार्वभौमिक हैं और फॉर्मूला का क्वांटिफायर-मुक्त हिस्सा [[ हॉर्न उपवाक्य ]] फॉर्म में है, जिसका अर्थ है कि यह एक बड़ा और है OR का, और प्रत्येक OR में संभवतः एक को छोड़कर प्रत्येक चर को नकार दिया गया है।
+एसओ-हॉर्न एसओ सूत्रों के साथ डिजंक्टिव सामान्य रूप में परिभाषित बूलियन प्रश्नों का सेट है, जैसे कि प्रथम-क्रम क्वांटिफायर सभी सार्वभौमिक हैं और फॉर्मूला का क्वांटिफायर-मुक्त हिस्सा [[ हॉर्न उपवाक्य ]] फॉर्म में है, जिसका अर्थ है कि यह एक बड़ा और है OR का, और प्रत्येक OR में संभवतः एक को छोड़कर प्रत्येक वेरिएबल को अस्वीकार दिया गया है।
-यह वर्ग उत्तराधिकारी फ़ंक्शन वाली संरचनाओं पर पी (जटिलता) के बराबर है।<ref>{{Cite journal|last=Grädel|first=Erich|date=1992-07-13|title=दूसरे क्रम के तर्क के टुकड़ों द्वारा जटिलता वर्गों को कैप्चर करना|journal=Theoretical Computer Science|language=en|volume=101|issue=1|pages=35–57|doi=10.1016/0304-3975(92)90149-A|issn=0304-3975|doi-access=free}}</ref>
+यह वर्ग उत्तराधिकारी फ़ंक्शन वाली संरचनाओं पर पी (कॉम्प्लेक्सिटी) के समान  है।<ref>{{Cite journal|last=Grädel|first=Erich|date=1992-07-13|title=दूसरे क्रम के तर्क के टुकड़ों द्वारा जटिलता वर्गों को कैप्चर करना|journal=Theoretical Computer Science|language=en|volume=101|issue=1|pages=35–57|doi=10.1016/0304-3975(92)90149-A|issn=0304-3975|doi-access=free}}</ref> उन सूत्रों को अस्तित्वगत दूसरे क्रम के हॉर्न लॉजिक में प्रीनेक्स सूत्रों में बदला जा सकता है।<ref name=":2" />
-उन सूत्रों को अस्तित्वगत दूसरे क्रम के हॉर्न लॉजिक में प्रीनेक्स सूत्रों में बदला जा सकता है।<ref name=":2" />
@@ Line 65: / Line 67: @@
 === फागिन का प्रमेय ===
-रोनाल्ड फागिन का 1974 का प्रमाण कि जटिलता वर्ग एनपी को अस्तित्वगत दूसरे क्रम के तर्क में स्वयंसिद्ध संरचनाओं के उन वर्गों द्वारा सटीक रूप से चित्रित किया गया था, जो वर्णनात्मक जटिलता सिद्धांत का प्रारंभिक बिंदु था।<ref name=":1" /><ref>Immerman 1999, p. 115</ref>
+रोनाल्ड फागिन का 1974 का प्रमाण कि कॉम्प्लेक्सिटी वर्ग एनपी को अस्तित्वगत दूसरे क्रम के लॉजिक  में स्वयंसिद्ध संरचनाओं के उन वर्गों द्वारा स्पष्ट  रूप से चित्रित किया गया था, जो डिस्क्रिप्टिव कॉम्प्लेक्सिटी थ्योरी  का प्रारंभिक बिंदु था।<ref name=":1" /><ref>Immerman 1999, p. 115</ref>
-चूंकि अस्तित्व संबंधी सूत्र का पूरक एक सार्वभौमिक सूत्र है, इसलिए यह तुरंत ही अनुसरण करता है कि सह-एनपी को सार्वभौमिक दूसरे क्रम के तर्क की विशेषता है।<ref name=":1" />
-एसओ, अप्रतिबंधित दूसरे क्रम का तर्क, [[बहुपद पदानुक्रम]] के बराबर है। अधिक सटीक रूप से, हमारे पास फागिन के प्रमेय का निम्नलिखित सामान्यीकरण है: प्रीनेक्स सामान्य रूप में सूत्रों का सेट जहां दूसरे क्रम के अस्तित्वगत और सार्वभौमिक क्वांटिफायर वैकल्पिक के बार बहुपद पदानुक्रम के केवें स्तर को दर्शाते हैं।<ref>Immerman 1999, p. 121</ref>
+चूंकि अस्तित्व संबंधी सूत्र का पूरक एक सार्वभौमिक सूत्र है, इसलिए यह तुरंत ही अनुसरण करता है कि सह-एनपी को सार्वभौमिक दूसरे क्रम के लॉजिक  की विशेषता है।<ref name=":1" />
-जटिलता वर्गों के अधिकांश अन्य लक्षणों के विपरीत, फागिन का प्रमेय और इसका सामान्यीकरण संरचनाओं पर कुल आदेश का अनुमान नहीं लगाता है। ऐसा इसलिए है क्योंकि अस्तित्वगत दूसरे क्रम का तर्क स्वयं दूसरे क्रम के चर का उपयोग करके संरचना पर संभावित कुल आदेशों को संदर्भित करने के लिए पर्याप्त रूप से अभिव्यंजक है।<ref>Immerman 1999, p. 181</ref>
+एसओ, अप्रतिबंधित दूसरे क्रम का लॉजिक, [[बहुपद पदानुक्रम]] के समान  है। अधिक स्पष्ट  रूप से, हमारे पास फागिन के प्रमेय का निम्नलिखित सामान्यीकरण है: प्रीनेक्स सामान्य रूप में सूत्रों का सेट जहां दूसरे क्रम के अस्तित्वगत और सार्वभौमिक क्वांटिफायर वैकल्पिक के बार बहुपद पदानुक्रम के केवें स्तर को दर्शाते हैं।<ref>Immerman 1999, p. 121</ref>
+कॉम्प्लेक्सिटी वर्गों के अधिकांश अन्य लक्षणों के विपरीत फागिन का प्रमेय और इसका सामान्यीकरण संरचनाओं पर कुल आदेश का अनुमान नहीं लगाता है। ऐसा इसलिए है क्योंकि अस्तित्वगत दूसरे क्रम का लॉजिक  स्वयं दूसरे क्रम के वेरिएबल का उपयोग करके संरचना पर संभावित कुल आदेशों को संदर्भित करने के लिए पर्याप्त रूप से अभिव्यंजक है।<ref>Immerman 1999, p. 181</ref>
 == एनपी से परे ==
-=== आंशिक निश्चित बिंदु PSPACE === है
+आंशिक निश्चित बिंदु PSPACE है
-बहुपद स्थान, पीएसपीएसीई में गणना योग्य सभी समस्याओं के वर्ग को अधिक अभिव्यंजक आंशिक निश्चित-बिंदु ऑपरेटर के साथ प्रथम-क्रम तर्क को बढ़ाकर चित्रित किया जा सकता है।
-[[आंशिक निश्चित-बिंदु तर्क]], एफओ [पीएफपी], आंशिक निश्चित-बिंदु ऑपरेटर के साथ प्रथम-क्रम तर्क का विस्तार है, जो एक सूत्र के निश्चित-बिंदु को व्यक्त करता है यदि कोई है और अन्यथा 'गलत' लौटाता है।
+बहुपद स्थान, पीएसपीएसीई में गणना योग्य सभी समस्याओं के वर्ग को अधिक अभिव्यंजक आंशिक निश्चित-बिंदु ऑपरेटर के साथ प्रथम-क्रम लॉजिक  को बढ़ाकर चित्रित किया जा सकता है।
-आंशिक निश्चित-बिंदु तर्क आदेशित संरचनाओं पर PSPACE की विशेषता बताता है।<ref>{{Cite journal|last1=Abiteboul|first1=S.|last2=Vianu|first2=V.|title=प्रथम-क्रम तर्क और डेटालॉग-जैसी भाषाओं के फिक्सपॉइंट एक्सटेंशन|url=http://dx.doi.org/10.1109/lics.1989.39160|journal=[1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science|year=1989|pages=71–79|publisher=IEEE Comput. Soc. Press|doi=10.1109/lics.1989.39160|isbn=0-8186-1954-6|s2cid=206437693}}</ref>
+[[आंशिक निश्चित-बिंदु तर्क|आंशिक निश्चित-बिंदु लॉजिक]] , एफओ [पीएफपी], आंशिक निश्चित-बिंदु ऑपरेटर के साथ प्रथम-क्रम लॉजिक  का विस्तार है, जो एक सूत्र के निश्चित-बिंदु को व्यक्त करता है यदि कोई है और अन्यथा 'गलत' लौटाता है।
+आंशिक निश्चित-बिंदु लॉजिक  आदेशित संरचनाओं पर PSPACE की विशेषता बताता है।<ref>{{Cite journal|last1=Abiteboul|first1=S.|last2=Vianu|first2=V.|title=प्रथम-क्रम तर्क और डेटालॉग-जैसी भाषाओं के फिक्सपॉइंट एक्सटेंशन|url=http://dx.doi.org/10.1109/lics.1989.39160|journal=[1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science|year=1989|pages=71–79|publisher=IEEE Comput. Soc. Press|doi=10.1109/lics.1989.39160|isbn=0-8186-1954-6|s2cid=206437693}}</ref>
-=== सकर्मक समापन PSPACE === है
+=== सकर्मक समापन PSPACE है ===
-दूसरे-क्रम के तर्क को पहले-क्रम के तर्क की तरह ही एक ट्रांजिटिव क्लोजर ऑपरेटर द्वारा बढ़ाया जा सकता है, जिसके परिणामस्वरूप SO[TC] होता है। टीसी ऑपरेटर अब तर्क के रूप में दूसरे क्रम के चर भी ले सकता है। SO[TC] PSPACE की विशेषता बताता है। चूंकि ऑर्डर को दूसरे क्रम के तर्क में संदर्भित किया जा सकता है, इसलिए यह लक्षण वर्णन ऑर्डर की गई संरचनाओं को नहीं मानता है।<ref>{{Cite journal|last1=Harel|first1=D.|last2=Peleg|first2=D.|date=1984-01-01|title=स्थिर तर्क, गतिशील तर्क और जटिलता वर्गों पर|journal=Information and Control|language=en|volume=60|issue=1|pages=86–102|doi=10.1016/S0019-9958(84)80023-6|issn=0019-9958|doi-access=free}}</ref>
+दूसरे-क्रम के लॉजिक  को पहले-क्रम के लॉजिक  की तरह ही एक ट्रांजिटिव क्लोजर ऑपरेटर द्वारा बढ़ाया जा सकता है, जिसके परिणामस्वरूप SO[TC] होता है। टीसी ऑपरेटर अब लॉजिक  के रूप में दूसरे क्रम के वेरिएबल भी ले सकता है। SO[TC] PSPACE की विशेषता बताता है। चूंकि ऑर्डर को दूसरे क्रम के लॉजिक  में संदर्भित किया जा सकता है, इसलिए यह लक्षण वर्णन ऑर्डर की गई संरचनाओं को नहीं मानता है।<ref>{{Cite journal|last1=Harel|first1=D.|last2=Peleg|first2=D.|date=1984-01-01|title=स्थिर तर्क, गतिशील तर्क और जटिलता वर्गों पर|journal=Information and Control|language=en|volume=60|issue=1|pages=86–102|doi=10.1016/S0019-9958(84)80023-6|issn=0019-9958|doi-access=free}}</ref>
 ==प्राथमिक कार्य==
-प्रारंभिक कार्यों के समय जटिलता वर्ग एलिमेंटरी को एचओ द्वारा चित्रित किया जा सकता है, संरचनाओं की जटिलता वर्ग जिसे उच्च-क्रम तर्क के सूत्रों द्वारा पहचाना जा सकता है। उच्च-क्रम तर्क, उच्च-क्रम परिमाणकों के साथ प्रथम-क्रम तर्क और द्वितीय-क्रम तर्क का विस्तार है। के बीच एक संबंध है <math>i</math>वें क्रम और गैर-नियतात्मक एल्गोरिदम जिसका समय सीमाबद्ध है <math>i-1</math> घातांक का स्तर.<ref>{{Cite journal| first1 = Lauri|last1= Hella|first2 = José María|last2 = Turull-Torres | title =उच्च-क्रम तर्कों के साथ प्रश्नों की गणना करना| journal =Theoretical Computer Science | volume = 355 | issue = 2 | year = 2006 | pages = 197–214   | issn =0304-3975 | publisher =Elsevier Science Publishers Ltd. | place =  Essex, UK | url = http://portal.acm.org/citation.cfm?id=1142890.1142897 | doi=10.1016/j.tcs.2006.01.009| doi-access = free }}</ref>
+प्रारंभिक कार्यों के समय कॉम्प्लेक्सिटी वर्ग एलिमेंटरी को एचओ द्वारा चित्रित किया जा सकता है, संरचनाओं की कॉम्प्लेक्सिटी वर्ग जिसे उच्च-क्रम लॉजिक  के सूत्रों द्वारा पहचाना जा सकता है।  उच्च-क्रम तर्क, उच्च-क्रम परिमाणकों के साथ प्रथम-क्रम तर्क और द्वितीय-क्रम तर्क का विस्तार है। <math>i</math>th क्रम और गैर-नियतात्मक एल्गोरिदम के बीच एक संबंध है जिसका समय घातांक के <math>i-1</math> स्तर से घिरा है।<ref>{{Cite journal| first1 = Lauri|last1= Hella|first2 = José María|last2 = Turull-Torres | title =उच्च-क्रम तर्कों के साथ प्रश्नों की गणना करना| journal =Theoretical Computer Science | volume = 355 | issue = 2 | year = 2006 | pages = 197–214   | issn =0304-3975 | publisher =Elsevier Science Publishers Ltd. | place =  Essex, UK | url = http://portal.acm.org/citation.cfm?id=1142890.1142897 | doi=10.1016/j.tcs.2006.01.009| doi-access = free }}</ref>
 === परिभाषा ===
-हम उच्च-क्रम वाले चर परिभाषित करते हैं। क्रम का एक चर <math>i>1</math> एक योग्यता है <math>k</math> और किसी भी सेट का प्रतिनिधित्व करता है <math>k</math>-क्रम के तत्वों के टुपल्स <math>i-1</math>. वे आम तौर पर बड़े अक्षरों में लिखे जाते हैं और क्रम को इंगित करने के लिए घातांक के रूप में एक प्राकृतिक संख्या के साथ लिखे जाते हैं। उच्च-क्रम तर्क प्रथम-क्रम सूत्रों का सेट है जहां हम उच्च-क्रम चर पर मात्रा का ठहराव जोड़ते हैं; इसलिए हम [[एफओ (जटिलता)]] लेख में परिभाषित शब्दों को दोबारा परिभाषित किए बिना उनका उपयोग करेंगे।
+हम उच्च-क्रम वाले चर परिभाषित करते हैं। क्रम <math>i>1</math> के एक चर में एक एरीटी <math>k</math>  है और क्रम <math>i-1</math>के तत्वों के <math>k</math>-टुपल्स के किसी भी सेट का प्रतिनिधित्व करता है। वे समान्यत: बड़े अक्षरों में लिखे जाते हैं और क्रम को निरुपित करने के लिए घातांक के रूप में एक प्राकृतिक संख्या के साथ लिखे जाते हैं। उच्च-क्रम तर्क प्रथम-क्रम सूत्रों का सेट है जहां हम उच्च-क्रम चर पर मात्रा का ठहराव जोड़ते हैं; इसलिए हम एफओ लेख में परिभाषित शब्दों को दोबारा परिभाषित किए बिना उनका उपयोग करेंगे।
-हो<math>^i</math> अधिकतम क्रम के चर वाले सूत्रों का समूह है <math>i</math>. को<math>^i_j</math> फॉर्म के सूत्रों का सबसेट है <math>\phi=\exists \overline{X^i_1}\forall\overline{X_2^i}\dots Q \overline{X_j^i}\psi</math>, कहाँ <math>Q</math> एक परिमाणक है और <math>Q \overline{X^i}</math> मतलब कि <math>\overline{X^i}</math> क्रम के चर का एक टुपल है <math>i</math> उसी परिमाणीकरण के साथ. तो हो<math>^i_j</math> के साथ सूत्रों का सेट है <math>j</math> क्रम के परिमाणकों का विकल्प <math>i</math>, इसके साथ शुरुआत <math>\exists</math>, उसके बाद क्रम का एक सूत्र आता है <math>i-1</math>.
+HO<math>^i</math> अधिiम <math>i</math> क्रम के चर वाले सूत्रों का समूह है। HO<math>^i_j</math> फॉर्म के सूत्रों का सबसेट है <math>\phi=\exists \overline{X^i_1}\forall\overline{X_2^i}\dots Q \overline{X_j^i}\psi</math> जहां <math>Q</math> एक क्वांटिफायर है और <math>Q \overline{X^i}</math> का मतलब है कि <math>\overline{X^i}</math> समान क्वांटिफिकेशन के साथ ऑर्डर i के वेरिएबल का एक टुपल है। तो HO<math>^i_j</math> क्रम <math>i</math> के क्वांटिफायर के <math>j</math> विकल्पों के साथ सूत्रों का सेट है, जो <math>\exists</math> से शुरू होता है, उसके बाद क्रम <math>i-1</math> का एक सूत्र होता है।
-Tetration#नोटेशन के मानक नोटेशन का उपयोग करते हुए, <math>\exp_2^0(x)=x</math> और <math> \exp_2^{i+1}(x)=2^{\exp_2^{i}(x)}</math>. <math> \exp_2^{i+1}(x)=2^{2^{2^{2^{\dots^{2^{x}}}}}}</math> साथ <math>i</math> टाइम्स <math>2</math>
+टेट्रेशन के मानक नोटेशन का उपयोग करते हुए, <math>\exp_2^0(x)=x</math> और <math> \exp_2^{i+1}(x)=2^{\exp_2^{i}(x)}</math>. <math> \exp_2^{i+1}(x)=2^{2^{2^{2^{\dots^{2^{x}}}}}}</math> साथ <math>i</math> गुना <math>2</math> है
 === सामान्य रूप ===
-क्रम का हर सूत्र <math>i</math>यह प्रीनेक्स सामान्य रूप में एक सूत्र के बराबर है, जहां हम पहले चर के ऊपर मात्रा का ठहराव लिखते हैं <math>i</math>वां क्रम और फिर क्रम का एक सूत्र <math>i-1</math> सामान्य रूप में.
+ऑर्डर <math>i</math>वां का प्रत्येक सूत्र प्रीनेक्स सामान्य रूप में एक सूत्र के समान  है, जहां हम <math>i</math>वां  ऑर्डर के चर पर मात्रा का ठहराव लिखते हैं और फिर सामान्य रूप में <math>i-1</math> का एक सूत्र लिखते हैं।
-=== जटिलता वर्गों से संबंध ===
+=== कॉम्प्लेक्सिटी वर्गों से संबंध ===
-एचओ प्राथमिक कार्यों के वर्ग एलिमेंटरी के बराबर है। अधिक स्पष्ट करने के लिए, <math>\mathsf{HO}^i_0 = \mathsf{NTIME}(\exp_2^{i-2}(n^{O(1)}))</math>, जिसका अर्थ है एक मीनार <math>(i-2)</math> 2s, के साथ समाप्त हो रहा है <math>n^c</math>, कहाँ <math>c</math> एक स्थिरांक है. इसका एक विशेष मामला यह है कि एनपी (जटिलता)|<math>\exists\mathsf{SO}=\mathsf{HO}^2_0=\mathsf{NTIME}(n^{O(1)})={\color{Blue}\mathsf{NP}}</math>, जो बिल्कुल फेगिन का प्रमेय है। बहुपद पदानुक्रम में [[ओरेकल मशीन]]ों का उपयोग करना, NTIME|<math>\mathsf{HO}^i_j={\color{Blue}\mathsf{NTIME}}(\exp_2^{i-2}(n^{O(1)})^{\Sigma_j^{\mathsf P}})</math>
+एचओ प्राथमिक कार्यों के वर्ग एलिमेंटरी के समान  है। अधिक स्पष्ट होने के लिए, <math>\mathsf{HO}^i_0 = \mathsf{NTIME}(\exp_2^{i-2}(n^{O(1)}))</math>, जिसका अर्थ है <math>(i-2)</math>2s का एक टावर, जो <math>n^c</math> पर समाप्त होता है, जहां <math>c</math> एक स्थिरांक है। इसका एक विशेष मामला यह है कि <math>\exists\mathsf{SO}=\mathsf{HO}^2_0=\mathsf{NTIME}(n^{O(1)})={\color{Blue}\mathsf{NP}}</math>, जो बिल्कुल फेगिन का प्रमेय है। बहुपद पदानुक्रम में ओरेकल मशीनों का उपयोग करना <math>\mathsf{HO}^i_j={\color{Blue}\mathsf{NTIME}}(\exp_2^{i-2}(n^{O(1)})^{\Sigma_j^{\mathsf P}})</math> है .
 ==टिप्पणियाँ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 16:08, 25 July 2023

Contents

सेटिंग

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