प्राथमिक: Difference between revisions

Revision as of 16:00, 24 May 2023

कम्प्यूटेशनल जटिलता सिद्धांत में प्राथमिक पुनरावर्ती कार्यों की जटिलता वर्ग प्राथमिक कक्षाओं का संघ है

{\begin{aligned}{\mathsf {ELEMENTARY}}&=\bigcup _{k\in \mathbb {N} }k{\mathsf {{\mbox{-}}EXP}}\\&={\mathsf {DTIME}}\left(2^{n}\right)\cup {\mathsf {DTIME}}\left(2^{2^{n}}\right)\cup {\mathsf {DTIME}}\left(2^{2^{2^{n}}}\right)\cup \cdots \end{aligned}}

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

LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R

जबकि प्राथमिक में घातांक के सीमित अनुप्रयोग होते हैं (उदाहरण के लिए, $O(2^{2^{n}})$ ), PR (जटिलता) अधिक सामान्य हाइपर ऑपरेटरों (उदाहरण के लिए टेट्रेशन) की अनुमति देता है जो प्राथमिक में सम्मिलित नहीं हैं।

परिभाषा

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

जीरो कार्य शून्य लौटाता है: f(x) = 0।
उत्तराधिकारी कार्य: f(x) = x + 1. अधिकांशतः इसे S द्वारा निरूपित किया जाता है, जैसा कि S(x) में होता है एक उत्तराधिकारी कार्य के बार-बार आवेदन के माध्यम से कोई अतिरिक्त प्राप्त कर सकता है।
प्रक्षेपण कार्य: इनका उपयोग तर्कों को अनदेखा करने के लिए किया जाता है। उदाहरण के लिए, f(a, b) = a एक प्रक्षेपण फलन है।
घटाव कार्य: f(x, y) = x - y यदि y <'x, या 0 यदि y ≥ x इस कार्य का उपयोग नियमबद्ध और पुनरावृत्ति को परिभाषित करने के लिए किया जाता है।

इन मूलभूत कार्यों से हम अन्य प्राथमिक पुनरावर्ती कार्यों का निर्माण कर सकते हैं।

संरचना: कुछ प्राथमिक पुनरावर्ती कार्य से मानो को दूसरे प्राथमिक पुनरावर्ती कार्य के तर्क के रूप में प्रयुक्त करना। f(x₁, ..., x_n) = h(g₁(x₁, ..., x_n), ..., g_m(x₁, ..., x_n)) प्राथमिक पुनरावर्ती है यदि h प्राथमिक पुनरावर्ती है और प्रत्येक g_i प्राथमिक पुनरावर्ती है।
परिबद्ध योग: $f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})$ प्राथमिक पुनरावर्ती है यदि जी प्राथमिक पुनरावर्ती है।
'बाध्य उत्पाद': $f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})$ प्राथमिक पुनरावर्ती है यदि जी प्राथमिक पुनरावर्ती है।

प्राथमिक के लिए आधार

प्रारंभिक कार्यों का वर्ग अनुमानों की संरचना के संबंध में बंद होने के साथ मेल खाता है और निम्न कार्य सेटों में से एक है: $\{n+1,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,n^{m}\}$ , $\{n+m,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,2^{n}\}$ , $\{n+m,n^{2},n\,{\bmod {\,}}m,2^{n}\}$ , कहाँ $n\,{\stackrel {.}{-}}\,m=\max\{n-m,0\}$ ऊपर परिभाषित घटाव कार्य है।^[1]^[2]

निम्न प्राथमिक पुनरावर्ती कार्य

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

निम्न प्राथमिक कार्यों की श्रेणी में सरल कार्यों की संरचना के संदर्भ में एक विवरण है जो हमारे पास प्राथमिक कार्यों के लिए है।^[3]^[4] अर्थात्, एक बहुपद-बद्ध कार्य निम्न प्राथमिक है यदि और केवल यदि इसे निम्नलिखित कार्यों की संरचना का उपयोग करके व्यक्त किया जा सकता है: अनुमान, $n+1$ , $nm$ , $n\,{\stackrel {.}{-}}\,m$ \,m, $n\wedge m$ $\lfloor n/m\rfloor$ , एक एक्सपोनेंशियल फंक्शन ( $2^{n}$ या $n^{m}$ ) सूत्रों की संरचना पर निम्नलिखित प्रतिबंध के साथ: सूत्र एक घातांक के संबंध में दो से अधिक तल नहीं हो सकते (उदाहरण के लिए, $xy(z+1)$ में 1 तल है, $(x+y)^{yz+x}+z^{x+1}$ में 2 तल हैं, $2^{2^{x}}$ में 3 तल हैं)। यहाँ $n\wedge m$ एक बिटवाइज़ AND का $n$ और $m$ है.

वर्णनात्मक लक्षण वर्णन

वर्णनात्मक जटिलता में एलिमेंटरी भाषा के वर्ग HO के सामान्य है जिसे उच्च-क्रम तर्क के एक सूत्र द्वारा वर्णित किया जा सकता है^[5]। इसका अर्थ यह है कि प्राथमिक जटिलता वर्ग में प्रत्येक भाषा एक उच्च-क्रम सूत्र के रूप में मेल खाती है जो भाषा के तत्वों के लिए और केवल के लिए सही है। अधिक स्पष्टता से ${\mathsf {NTIME}}\left(2^{2^{\cdots {2^{O(n)}}}}\right)=\exists {}{\mathsf {HO}}^{i}$ }, जहां ⋯ $i$ घातांक के एक टावर को इंगित करता है और $\exists {}{\mathsf {HO}}^{i}$ प्रश्नों का वर्ग है जो $i$ वें क्रम के अस्तित्वपरक परिमाणकों से प्रारंभ होता है और फिर $(i - 1)$ वें क्रम का एक सूत्र है।

यह भी देखें

प्राथमिक कार्य अंकगणित
आदिम पुनरावर्ती कार्य
ग्रेज़गोर्स्की पदानुक्रम
एक्सपटाइम

↑ Mazzanti, S (2002). "आदिम पुनरावर्ती कार्यों की कक्षाओं के लिए सादा आधार". Mathematical Logic Quarterly. 48: 93–104. doi:10.1002/1521-3870(200201)48:1<93::aid-malq93>3.0.co;2-8.
↑ S. S. Marchenkov, "Superpositions of elementary arithmetic functions", Journal of Applied and Industrial Mathematics, September 2007, Volume 1, Issue 3, pp 351-360, doi:10.1134/S1990478907030106.
↑ Th. Skolem, "Proof of some theorems on recursively enumerable sets", Notre Dame Journal of Formal Logic, 1962, Volume 3, Number 2, pp 65-74, doi:10.1305/ndjfl/1093957149.
↑ एस ए वोल्कोव, स्कोलेम प्राथमिक कार्यों की कक्षा पर, अनुप्रयुक्त और औद्योगिक गणित जर्नल, 2010, खंड 4, अंक 4, पीपी 588-599, doi:10.1134/S1990478910040149.</रेफरी> जबकि प्राथमिक पुनरावर्ती कार्यों में घातीय वृद्धि की तुलना में संभावित रूप से अधिक है, निम्न प्राथमिक पुनरावर्ती कार्यों में बहुपद वृद्धि होती है। निम्न प्राथमिक कार्यों के वर्ग में सरल कार्यों की संरचना के संदर्भ में विवरण होता है जो हमारे पास प्राथमिक कार्यों के लिए होता है।<ref>Volkov, Sergey (2016). "Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions [dissertation]". arXiv:1611.04843.
↑ Lauri Hella and José María Turull-Torres (2006), "Computing queries with higher-order logics", Theoretical Computer Science, 355 (2): 197–214, doi:10.1016/j.tcs.2006.01.009, ISSN 0304-3975

संदर्भ

Rose, H.E., Subrecursion: Functions and hierarchies, Oxford University Press, 1984. ISBN 0-19-853189-3

[1] Mazzanti, S (2002). "आदिम पुनरावर्ती कार्यों की कक्षाओं के लिए सादा आधार". Mathematical Logic Quarterly. 48: 93–104. doi:10.1002/1521-3870(200201)48:1<93::aid-malq93>3.0.co;2-8.

[2] S. S. Marchenkov, "Superpositions of elementary arithmetic functions", Journal of Applied and Industrial Mathematics, September 2007, Volume 1, Issue 3, pp 351-360, doi:10.1134/S1990478907030106.

[3] Th. Skolem, "Proof of some theorems on recursively enumerable sets", Notre Dame Journal of Formal Logic, 1962, Volume 3, Number 2, pp 65-74, doi:10.1305/ndjfl/1093957149.

[volkov_skolem-4] एस ए वोल्कोव, स्कोलेम प्राथमिक कार्यों की कक्षा पर, अनुप्रयुक्त और औद्योगिक गणित जर्नल, 2010, खंड 4, अंक 4, पीपी 588-599, doi:10.1134/S1990478910040149.</रेफरी> जबकि प्राथमिक पुनरावर्ती कार्यों में घातीय वृद्धि की तुलना में संभावित रूप से अधिक है, निम्न प्राथमिक पुनरावर्ती कार्यों में बहुपद वृद्धि होती है। निम्न प्राथमिक कार्यों के वर्ग में सरल कार्यों की संरचना के संदर्भ में विवरण होता है जो हमारे पास प्राथमिक कार्यों के लिए होता है।<ref>Volkov, Sergey (2016). "Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions [dissertation]". arXiv:1611.04843.

[5] Lauri Hella and José María Turull-Torres (2006), "Computing queries with higher-order logics", Theoretical Computer Science, 355 (2): 197–214, doi:10.1016/j.tcs.2006.01.009, ISSN 0304-3975

[1]

[2]

[3]

[4]

[5]

@@ Line 1: / Line 1: @@
-{{About| |other meanings|Elementary (disambiguation){{!}}Elementary}}
+{{About| |अन्य अर्थ|प्राथमिक (बहुविकल्पी){{!}}प्राथमिक}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, प्राथमिक पुनरावर्ती कार्यों की [[जटिलता वर्ग]] प्राथमिक कक्षाओं का संघ है
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में प्राथमिक पुनरावर्ती कार्यों की [[जटिलता वर्ग]] प्राथमिक कक्षाओं का संघ है
 : <math> \begin{align}
@@ Line 8: / Line 8: @@
    \end{align}
 </math>
-संगणनीय कार्य और [[अनिर्णीत समस्या]] के संदर्भ में, नाम László Kalmár द्वारा गढ़ा गया था; इसमें अधिकांश समस्याएं प्राथमिक से दूर हैं। कुछ प्राकृतिक पुनरावर्ती समस्याएं प्राथमिक के बाहर हैं, और इस प्रकार गैर-प्राथमिक हैं। विशेष रूप से, [[आदिम पुनरावर्ती]] समस्याएं हैं जो प्राथमिक में नहीं हैं। हम जानते हैं
+संगणनीय कार्य और [[अनिर्णीत समस्या]] के संदर्भ में, नाम लास्ज़्लो कलमर द्वारा गढ़ा गया था; इसमें अधिकांश समस्याएं प्राथमिक से दूर हैं। कुछ प्राकृतिक पुनरावर्ती समस्याएं प्राथमिक के बाहर हैं, और इस प्रकार गैर-प्राथमिक हैं। विशेष रूप से [[आदिम पुनरावर्ती]] समस्याएं हैं जो प्राथमिक में नहीं हैं। हम जानते हैं
-:निम्न-प्राथमिक ⊊ अनुभव ⊊ प्राथमिक ⊊ पी[[आर (जटिलता)]] ⊊ आर (जटिलता)
+:: LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R
-जबकि ELEMENTARY में [[घातांक]] के सीमित अनुप्रयोग होते हैं (उदाहरण के लिए, <math>O(2^{2^n})</math>), पीआर (जटिलता) अधिक सामान्य [[हाइपर ऑपरेटर]]ों (उदाहरण के लिए, [[टेट्रेशन]]) की अनुमति देता है जो प्राथमिक में शामिल नहीं हैं।
+जबकि प्राथमिक में [[घातांक]] के सीमित अनुप्रयोग होते हैं (उदाहरण के लिए, <math>O(2^{2^n})</math>), PR  (जटिलता) अधिक सामान्य [[हाइपर ऑपरेटर|हाइपर ऑपरेटरों]] (उदाहरण के लिए [[टेट्रेशन]]) की अनुमति देता है जो प्राथमिक में सम्मिलित नहीं हैं।
 == परिभाषा ==
-प्राथमिक पुनरावर्ती कार्यों की परिभाषाएँ [[आदिम पुनरावर्ती कार्य]]ों के लिए समान हैं, सिवाय इसके कि आदिम पुनरावर्तन को परिबद्ध योग और परिबद्ध उत्पाद द्वारा प्रतिस्थापित किया जाता है। सभी कार्य [[प्राकृतिक संख्या]]ओं पर काम करते हैं। बुनियादी कार्य, उनमें से सभी प्राथमिक पुनरावर्ती हैं:
+प्राथमिक पुनरावर्ती कार्यों की परिभाषाएँ [[आदिम पुनरावर्ती कार्य]] के लिए समान हैं अतिरिक्त इसके कि आदिम पुनरावर्तन को परिबद्ध योग और परिबद्ध उत्पाद द्वारा प्रतिस्थापित किया जाता है। सभी कार्य [[प्राकृतिक संख्या]]ओं पर काम करते हैं। मूलभूत कार्य उनमें से सभी प्राथमिक पुनरावर्ती हैं:
-# जीरो फंक्शन। शून्य लौटाता है: ''f''(x) = 0।
+# जीरो कार्य शून्य लौटाता है: ''f''(x) = 0।
-# उत्तराधिकारी कार्य: ''f''(''x'') = ''x'' + 1. अक्सर इसे ''S'' द्वारा निरूपित किया जाता है, जैसा कि ''S''(''x'') में होता है . एक उत्तराधिकारी समारोह के बार-बार आवेदन के माध्यम से, कोई अतिरिक्त प्राप्त कर सकता है।
+# उत्तराधिकारी कार्य: ''f''(''x'') = ''x'' + 1. अधिकांशतः इसे ''S'' द्वारा निरूपित किया जाता है, जैसा कि ''S''(''x'') में होता है एक उत्तराधिकारी कार्य के बार-बार आवेदन के माध्यम से कोई अतिरिक्त प्राप्त कर सकता है।
-# प्रक्षेपण कार्य: इनका उपयोग तर्कों को अनदेखा करने के लिए किया जाता है। उदाहरण के लिए, ''f''(''a'', ''b'') = ''a'' एक प्रोजेक्शन फंक्शन है।
+# प्रक्षेपण कार्य: इनका उपयोग तर्कों को अनदेखा करने के लिए किया जाता है। उदाहरण के लिए, ''f''(''a'', ''b'') = ''a'' एक प्रक्षेपण फलन है।
-# घटाव फ़ंक्शन: ''f''(''x'', ''y'') = ''x'' - ''y'' अगर ''y'' <'x'', या 0 अगर ''वाई'' ≥ ''एक्स''। इस फ़ंक्शन का उपयोग सशर्त और पुनरावृत्ति को परिभाषित करने के लिए किया जाता है।
+# घटाव कार्य: ''f''(''x'', ''y'') = ''x'' - ''y'' यदि  ''y'' <'x'', या 0 यदि  y'' ≥ ''x इस कार्य का उपयोग नियमबद्ध और पुनरावृत्ति को परिभाषित करने के लिए किया जाता है।''
-इन बुनियादी कार्यों से, हम अन्य प्राथमिक पुनरावर्ती कार्यों का निर्माण कर सकते हैं।
+इन मूलभूत कार्यों से हम अन्य प्राथमिक पुनरावर्ती कार्यों का निर्माण कर सकते हैं।
-# संरचना: कुछ प्राथमिक पुनरावर्ती फ़ंक्शन से मूल्यों को दूसरे प्राथमिक पुनरावर्ती फ़ंक्शन के तर्क के रूप में लागू करना। ''च''(''x'' में<sub>1</sub>, ..., एक्स<sub>n</sub>) = एच (जी<sub>1</sub>(एक्स<sub>1</sub>, ..., एक्स<sub>n</sub>), ..., जी<sub>m</sub>(एक्स<sub>1</sub>, ..., एक्स<sub>n</sub>)) प्राथमिक पुनरावर्ती है यदि h प्राथमिक पुनरावर्ती है और प्रत्येक g<sub>i</sub> प्राथमिक पुनरावर्ती है।
+# संरचना: कुछ प्राथमिक पुनरावर्ती कार्य से मानो को दूसरे प्राथमिक पुनरावर्ती कार्य के तर्क के रूप में प्रयुक्त करना।  ''f''(''x''<sub>1</sub>, ..., ''x''<sub>n</sub>) = ''h''(''g''<sub>1</sub>(''x''<sub>1</sub>, ..., ''x''<sub>n</sub>), ..., ''g''<sub>m</sub>(''x''<sub>1</sub>, ..., ''x''<sub>n</sub>))  प्राथमिक पुनरावर्ती है यदि h प्राथमिक पुनरावर्ती है और प्रत्येक g<sub>i</sub> प्राथमिक पुनरावर्ती है।
 # परिबद्ध योग: <math>f(m, x_1, \ldots, x_n) = \sum\limits_{i=0}^mg(i, x_1, \ldots, x_n)</math> प्राथमिक पुनरावर्ती है यदि जी प्राथमिक पुनरावर्ती है।
 # 'बाध्य उत्पाद': <math>f(m, x_1, \ldots, x_n) = \prod\limits_{i=0}^mg(i, x_1, \ldots, x_n)</math> प्राथमिक पुनरावर्ती है यदि जी प्राथमिक पुनरावर्ती है।
@@ Line 31: / Line 31: @@
 == प्राथमिक के लिए आधार ==
-प्रारंभिक कार्यों का वर्ग अनुमानों की संरचना के संबंध में बंद होने के साथ मेल खाता है और निम्न फ़ंक्शन सेटों में से एक है: <math>\{ n+1, n \,\stackrel{.}{-}\, m, \lfloor n/m \rfloor, n^m \}</math>, <math>\{ n+m, n \,\stackrel{.}{-}\, m, \lfloor n/m\rfloor, 2^n \}</math>, <math>\{ n+m, n^2, n \,\bmod\, m, 2^n \}</math>, कहाँ <math>n \, \stackrel{.}{-} \, m = \max\{n-m, 0\}</math> ऊपर परिभाषित घटाव कार्य है।<ref>{{cite journal | last1 = Mazzanti | first1 = S | year = 2002 | title = आदिम पुनरावर्ती कार्यों की कक्षाओं के लिए सादा आधार| journal = Mathematical Logic Quarterly | volume = 48 | pages = 93–104 | doi=10.1002/1521-3870(200201)48:1<93::aid-malq93>3.0.co;2-8}}</ref><ref>S. S. Marchenkov, "Superpositions of elementary arithmetic functions", ''Journal of Applied and Industrial Mathematics'', September 2007, Volume 1, Issue 3, pp 351-360, {{doi|10.1134/S1990478907030106}}.</ref>
+प्रारंभिक कार्यों का वर्ग अनुमानों की संरचना के संबंध में बंद होने के साथ मेल खाता है और निम्न कार्य सेटों में से एक है: <math>\{ n+1, n \,\stackrel{.}{-}\, m, \lfloor n/m \rfloor, n^m \}</math>, <math>\{ n+m, n \,\stackrel{.}{-}\, m, \lfloor n/m\rfloor, 2^n \}</math>, <math>\{ n+m, n^2, n \,\bmod\, m, 2^n \}</math>, कहाँ <math>n \, \stackrel{.}{-} \, m = \max\{n-m, 0\}</math> ऊपर परिभाषित घटाव कार्य है।<ref>{{cite journal | last1 = Mazzanti | first1 = S | year = 2002 | title = आदिम पुनरावर्ती कार्यों की कक्षाओं के लिए सादा आधार| journal = Mathematical Logic Quarterly | volume = 48 | pages = 93–104 | doi=10.1002/1521-3870(200201)48:1<93::aid-malq93>3.0.co;2-8}}</ref><ref>S. S. Marchenkov, "Superpositions of elementary arithmetic functions", ''Journal of Applied and Industrial Mathematics'', September 2007, Volume 1, Issue 3, pp 351-360, {{doi|10.1134/S1990478907030106}}.</ref>
 == निम्न प्राथमिक पुनरावर्ती कार्य ==
-निम्न प्रारंभिक पुनरावर्ती कार्य उपर्युक्त परिभाषाओं का पालन करते हैं, सिवाय इसके कि परिबद्ध उत्पाद की अनुमति नहीं है। यही है, एक निम्न प्राथमिक पुनरावर्ती कार्य शून्य, उत्तराधिकारी, या प्रक्षेपण कार्य, अन्य निम्न प्राथमिक पुनरावर्ती कार्यों की संरचना, या किसी अन्य निम्न प्राथमिक पुनरावर्ती कार्य की बाध्य राशि होना चाहिए।
+निम्न प्रारंभिक पुनरावर्ती कार्य उपर्युक्त परिभाषाओं का पालन करते हैं अतिरिक्त इसके कि परिबद्ध उत्पाद की अनुमति नहीं है। यही है एक निम्न प्राथमिक पुनरावर्ती कार्य शून्य उत्तराधिकारी या प्रक्षेपण कार्य अन्य निम्न प्राथमिक पुनरावर्ती कार्यों की संरचना या किसी अन्य निम्न प्राथमिक पुनरावर्ती कार्य की बाध्य राशि होना चाहिए।
-निम्न प्राथमिक पुनरावर्ती कार्यों को स्कोलेम प्राथमिक कार्यों के रूप में भी जाना जाता है।<ref>[[Thoralf Skolem|Th. Skolem]], "Proof of some theorems on recursively enumerable sets", ''[[Notre Dame Journal of Formal Logic]]'', 1962, Volume 3, Number 2, pp 65-74, {{doi|10.1305/ndjfl/1093957149}}.</ref><ref name="volkov_skolem">एस ए वोल्कोव, स्कोलेम प्राथमिक कार्यों की कक्षा पर, अनुप्रयुक्त और औद्योगिक गणित जर्नल, 2010, खंड 4, अंक 4, पीपी 588-599, {{doi|10.1134/S1990478910040149}}.</रेफरी>
+निम्न प्राथमिक कार्यों की श्रेणी में सरल कार्यों की संरचना के संदर्भ में एक विवरण है जो हमारे पास प्राथमिक कार्यों के लिए है।<ref>[[Thoralf Skolem|Th. Skolem]], "Proof of some theorems on recursively enumerable sets", ''[[Notre Dame Journal of Formal Logic]]'', 1962, Volume 3, Number 2, pp 65-74, {{doi|10.1305/ndjfl/1093957149}}.</ref><ref name="volkov_skolem">एस ए वोल्कोव, स्कोलेम प्राथमिक कार्यों की कक्षा पर, अनुप्रयुक्त और औद्योगिक गणित जर्नल, 2010, खंड 4, अंक 4, पीपी 588-599, {{doi|10.1134/S1990478910040149}}.</रेफरी>
 जबकि प्राथमिक पुनरावर्ती कार्यों में घातीय वृद्धि की तुलना में संभावित रूप से अधिक है, निम्न प्राथमिक पुनरावर्ती कार्यों में बहुपद वृद्धि होती है।
-निम्न प्राथमिक कार्यों के वर्ग में सरल कार्यों की संरचना के संदर्भ में विवरण होता है जो हमारे पास प्राथमिक कार्यों के लिए होता है।<ref name="volkov_skolem" /><ref>{{cite arXiv |last=Volkov |first=Sergey | year= 2016 |eprint=1611.04843 |title=Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions [dissertation] }}</ref> अर्थात्, एक बहुपद-सीमित फ़ंक्शन निम्न प्राथमिक है यदि और केवल यदि इसे निम्नलिखित कार्यों की संरचना का उपयोग करके व्यक्त किया जा सकता है: अनुमान, <math>n+1</math>, <math>nm</math>, <math>n \,\stackrel{.}{-}\, m</math>, <math>n\wedge m</math>, <math>\lfloor n/m \rfloor</math>, एक चरघातांकी फलन (<math>2^n</math> या <math>n^m</math>) सूत्रों की संरचना पर निम्नलिखित प्रतिबंध के साथ: सूत्र में एक घातांक के संबंध में दो से अधिक तल नहीं हो सकते (उदाहरण के लिए, <math>xy(z+1)</math> 1 मंजिल है, <math>(x+y)^{yz+x}+z^{x+1}</math> 2 मंजिलें हैं, <math>2^{2^x}</math> 3 मंजिलें हैं)। यहाँ <math>n\wedge m</math> एक बिटवाइज़ AND का है {{mvar|n}} और {{mvar|m}}.
+निम्न प्राथमिक कार्यों के वर्ग में सरल कार्यों की संरचना के संदर्भ में विवरण होता है जो हमारे पास प्राथमिक कार्यों के लिए होता है।<nowiki><ref></nowiki>{{cite arXiv |last=Volkov |first=Sergey | year= 2016 |eprint=1611.04843 |title=Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions [dissertation] }}</ref> अर्थात्, एक बहुपद-बद्ध कार्य निम्न प्राथमिक है यदि और केवल यदि इसे निम्नलिखित कार्यों की संरचना का उपयोग करके व्यक्त किया जा सकता है: अनुमान,<math>n+1</math>, <math>nm</math>, <math>n \,\stackrel{.}{-}\, m</math>\,m, <math>n\wedge m</math> <math>\lfloor n/m \rfloor</math>, एक एक्सपोनेंशियल फंक्शन (<math>2^n</math> या <math>n^m</math>) सूत्रों की संरचना पर निम्नलिखित प्रतिबंध के साथ: सूत्र एक घातांक के संबंध में दो से अधिक तल नहीं हो सकते (उदाहरण के लिए, <math>xy(z+1)</math> में 1 तल है, <math>(x+y)^{yz+x}+z^{x+1}</math> में 2 तल हैं, <math>2^{2^x}</math>में 3 तल हैं)। यहाँ <math>n\wedge m</math> एक बिटवाइज़ AND का  {{mvar|n}} और {{mvar|m}} है.
 == वर्णनात्मक लक्षण वर्णन ==
-[[वर्णनात्मक जटिलता]] में, प्राथमिक [[भाषा (कंप्यूटर विज्ञान)]] के वर्ग HO (जटिलता) के बराबर है जिसे उच्च-क्रम तर्क के सूत्र द्वारा वर्णित किया जा सकता है।<ref>{{Citation | author = Lauri Hella and José María Turull-Torres | title =Computing queries with higher-order logics | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 355 | issue = 2 | year = 2006 | pages = 197–214   | issn =0304-3975 | url = http://portal.acm.org/citation.cfm?id=1142890.1142897 | doi=10.1016/j.tcs.2006.01.009| doi-access = free }}</ref> इसका मतलब यह है कि प्राथमिक जटिलता वर्ग में प्रत्येक भाषा एक उच्च-क्रम सूत्र के रूप में मेल खाती है जो भाषा के तत्वों के लिए और केवल के लिए सही है। ज्यादा ठीक, <math>\mathsf{NTIME}\left(2^{2^{\cdots{2^{O(n)}}}}\right) = \exists{}\mathsf{HO}^i</math>, जहां ⋯ का एक टावर इंगित करता है {{mvar|i}} घातांक और <math>\exists{}\mathsf{HO}^i</math> प्रश्नों का वर्ग है जो के अस्तित्वपरक परिमाणकों से शुरू होता है {{mvar|i}}वें क्रम और फिर का एक सूत्र {{math|(''i''&nbsp;−&nbsp;1)}}वां आदेश।
+[[वर्णनात्मक जटिलता]] में एलिमेंटरी भाषा के वर्ग HO के सामान्य है जिसे उच्च-क्रम तर्क के एक सूत्र द्वारा वर्णित किया जा सकता है<ref>{{Citation | author = Lauri Hella and José María Turull-Torres | title =Computing queries with higher-order logics | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 355 | issue = 2 | year = 2006 | pages = 197–214   | issn =0304-3975 | url = http://portal.acm.org/citation.cfm?id=1142890.1142897 | doi=10.1016/j.tcs.2006.01.009| doi-access = free }}</ref>। इसका अर्थ यह है कि प्राथमिक जटिलता वर्ग में प्रत्येक भाषा एक उच्च-क्रम सूत्र के रूप में मेल खाती है जो भाषा के तत्वों के लिए और केवल के लिए सही है। अधिक स्पष्टता  से <math>\mathsf{NTIME}\left(2^{2^{\cdots{2^{O(n)}}}}\right) = \exists{}\mathsf{HO}^i</math>}, जहां ⋯ {{mvar|i}} घातांक के एक टावर को इंगित करता है और <math>\exists{}\mathsf{HO}^i</math> प्रश्नों का वर्ग है जो {{mvar|i}}वें क्रम के अस्तित्वपरक परिमाणकों से प्रारंभ होता है और फिर{{math|(''i''&nbsp;−&nbsp;1)}}वें क्रम का एक सूत्र है।
 == यह भी देखें ==
@@ Line 52: / Line 53: @@
 * आदिम पुनरावर्ती कार्य
 * ग्रेज़गोर्स्की पदानुक्रम
-* EXPTIME
+* एक्सपटाइम
 ==टिप्पणियाँ==

v t e Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Anonymous

Search

प्राथमिक: Difference between revisions

Namespaces

More

Page actions

Revision as of 16:00, 24 May 2023

Contents

परिभाषा

प्राथमिक के लिए आधार

निम्न प्राथमिक पुनरावर्ती कार्य

वर्णनात्मक लक्षण वर्णन

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

प्राथमिक: Difference between revisions

Revision as of 16:00, 24 May 2023

परिभाषा

प्राथमिक के लिए आधार

निम्न प्राथमिक पुनरावर्ती कार्य

वर्णनात्मक लक्षण वर्णन

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories