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

{{Short description|Branch of mathematical logic}}

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

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

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

==सेटिंग==

जब हम किसी कम्प्यूटेशनल समस्या का वर्णन करने के लिए तर्क औपचारिकता का उपयोग करते हैं, तो इनपुट एक सीमित संरचना है, और उस संरचना के तत्व [[प्रवचन का क्षेत्र]] हैं। आम तौर पर इनपुट या तो एक स्ट्रिंग (बिट्स या वर्णमाला के ऊपर) होता है और तार्किक संरचना के तत्व स्ट्रिंग की स्थिति का प्रतिनिधित्व करते हैं, या इनपुट एक ग्राफ़ होता है और तार्किक संरचना के तत्व इसके शीर्षों का प्रतिनिधित्व करते हैं। इनपुट की लंबाई संबंधित संरचना के आकार से मापी जाएगी।
संरचना जो भी हो, हम मान सकते हैं कि ऐसे संबंध हैं जिनका परीक्षण किया जा सकता है, उदाहरण के लिए<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>).

==जटिलता वर्गों की विशेषताओं का अवलोकन==
यदि हम खुद को उत्तराधिकारी संबंध और बुनियादी अंकगणितीय विधेय के साथ आदेशित संरचनाओं तक सीमित रखते हैं, तो हमें निम्नलिखित लक्षण मिलते हैं:
* [[प्रथम-क्रम तर्क]] वर्ग AC0|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 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>
* SO (जटिलता)|द्वितीय-क्रम तर्क 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>


== उप-बहुपद समय ==

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

[[सर्किट जटिलता]] में, मनमाना विधेय के साथ प्रथम-क्रम तर्क को 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>


=== [[सकर्मक समापन तर्क]] ===
प्रथम-क्रम तर्क को अभिव्यंजक शक्ति में काफी लाभ मिलता है जब इसे एक ऑपरेटर के साथ बढ़ाया जाता है जो बाइनरी संबंध के सकर्मक समापन की गणना करता है। परिणामी सकर्मक समापन तर्क को आदेशित संरचनाओं पर एनएल (जटिलता) | गैर-नियतात्मक लघुगणक स्थान (एनएल) को चिह्नित करने के लिए जाना जाता है। इसका उपयोग [[नील इमरमैन]] द्वारा यह दिखाने के लिए किया गया था कि एनएल पूरक के तहत बंद है (यानी एनएल = सह-एनएल)।<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>


== बहुपद [[समय]] ==
आदेशित संरचनाओं पर, प्रथम-क्रम न्यूनतम निश्चित-बिंदु तर्क 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>
2022 तक, यह अभी भी खुला है कि क्या अव्यवस्थित संरचनाओं पर 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>


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

एसओ-हॉर्न एसओ फ़ार्मुलों के साथ डिजंक्टिव सामान्य रूप में परिभाषित बूलियन प्रश्नों का सेट है, जैसे कि प्रथम-क्रम क्वांटिफायर सभी सार्वभौमिक हैं और फॉर्मूला का क्वांटिफायर-मुक्त हिस्सा [[ हॉर्न उपवाक्य ]] फॉर्म में है, जिसका अर्थ है कि यह एक बड़ा और है 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 name=":2" />


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

=== फागिन का प्रमेय ===
रोनाल्ड फागिन का 1974 का प्रमाण कि जटिलता वर्ग एनपी को अस्तित्वगत दूसरे क्रम के तर्क में स्वयंसिद्ध संरचनाओं के उन वर्गों द्वारा सटीक रूप से चित्रित किया गया था, जो वर्णनात्मक जटिलता सिद्धांत का प्रारंभिक बिंदु था।<ref name=":1" /><ref>Immerman 1999, p. 115</ref>
चूंकि अस्तित्व संबंधी सूत्र का पूरक एक सार्वभौमिक सूत्र है, इसलिए यह तुरंत ही अनुसरण करता है कि सह-एनपी को सार्वभौमिक दूसरे क्रम के तर्क की विशेषता है।<ref name=":1" /> 
एसओ, अप्रतिबंधित दूसरे क्रम का तर्क, [[बहुपद पदानुक्रम]] के बराबर है। अधिक सटीक रूप से, हमारे पास फागिन के प्रमेय का निम्नलिखित सामान्यीकरण है: प्रीनेक्स सामान्य रूप में सूत्रों का सेट जहां दूसरे क्रम के अस्तित्वगत और सार्वभौमिक क्वांटिफायर वैकल्पिक के बार बहुपद पदानुक्रम के केवें स्तर को दर्शाते हैं।<ref>Immerman 1999, p. 121</ref>
जटिलता वर्गों के अधिकांश अन्य लक्षणों के विपरीत, फागिन का प्रमेय और इसका सामान्यीकरण संरचनाओं पर कुल आदेश का अनुमान नहीं लगाता है। ऐसा इसलिए है क्योंकि अस्तित्वगत दूसरे क्रम का तर्क स्वयं दूसरे क्रम के चर का उपयोग करके संरचना पर संभावित कुल आदेशों को संदर्भित करने के लिए पर्याप्त रूप से अभिव्यंजक है।<ref>Immerman 1999, p. 181</ref>


== एनपी से परे ==

=== आंशिक निश्चित बिंदु 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 === है
दूसरे-क्रम के तर्क को पहले-क्रम के तर्क की तरह ही एक ट्रांजिटिव क्लोजर ऑपरेटर द्वारा बढ़ाया जा सकता है, जिसके परिणामस्वरूप 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>1</math> एक योग्यता है <math>k</math> और किसी भी सेट का प्रतिनिधित्व करता है <math>k</math>-क्रम के तत्वों के टुपल्स <math>i-1</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>.

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

==टिप्पणियाँ==
{{Reflist}}


== संदर्भ ==
* {{Cite book|first=Neil|last=Immerman|url=http://worldcat.org/oclc/901297152|title=Descriptive complexity|date=1999|publisher=Springer|isbn=0-387-98600-6|oclc=901297152}}


== बाहरी संबंध ==
* [http://www.cs.umass.edu/~immerman/descriptive_complexity.html Neil Immerman's descriptive complexity page], including a diagram
[[Category: वर्णनात्मक जटिलता| वर्णनात्मक जटिलता]] [[Category: कम्प्यूटेशनल जटिलता सिद्धांत]] [[Category: परिमित मॉडल सिद्धांत]] 



[[Category: Machine Translated Page]]
[[Category:Created On 20/07/2023]]