प्राथमिक

For other meanings, see Elementary.

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

${\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}}$

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

निम्न-प्राथमिक ⊊ अनुभव ⊊ प्राथमिक ⊊ पीआर (जटिलता) ⊊ आर (जटिलता)

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

परिभाषा

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

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

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

1. संरचना: कुछ प्राथमिक पुनरावर्ती फ़ंक्शन से मूल्यों को दूसरे प्राथमिक पुनरावर्ती फ़ंक्शन के तर्क के रूप में लागू करना। च(x में₁, ..., एक्स_n) = एच (जी₁(एक्स₁, ..., एक्स_n), ..., जी_m(एक्स₁, ..., एक्स_n)) प्राथमिक पुनरावर्ती है यदि h प्राथमिक पुनरावर्ती है और प्रत्येक g_i प्राथमिक पुनरावर्ती है।
2. परिबद्ध योग: $f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})$ प्राथमिक पुनरावर्ती है यदि जी प्राथमिक पुनरावर्ती है।
3. 'बाध्य उत्पाद': $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\}$ ऊपर परिभाषित घटाव कार्य है।

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

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

निम्न प्राथमिक पुनरावर्ती कार्यों को स्कोलेम प्राथमिक कार्यों के रूप में भी जाना जाता है। अर्थात्, एक बहुपद-सीमित फ़ंक्शन निम्न प्राथमिक है यदि और केवल यदि इसे निम्नलिखित कार्यों की संरचना का उपयोग करके व्यक्त किया जा सकता है: अनुमान, $n+1$, $nm$, $n\,{\stackrel {.}{-}}\,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 (जटिलता) के बराबर है जिसे उच्च-क्रम तर्क के सूत्र द्वारा वर्णित किया जा सकता है। इसका मतलब यह है कि प्राथमिक जटिलता वर्ग में प्रत्येक भाषा एक उच्च-क्रम सूत्र के रूप में मेल खाती है जो भाषा के तत्वों के लिए और केवल के लिए सही है। ज्यादा ठीक, ${\mathsf {NTIME}}\left(2^{2^{\cdots {2^{O(n)}}}}\right)=\exists {}{\mathsf {HO}}^{i}$, जहां ⋯ का एक टावर इंगित करता है i घातांक और $\exists {}{\mathsf {HO}}^{i}$ प्रश्नों का वर्ग है जो के अस्तित्वपरक परिमाणकों से शुरू होता है iवें क्रम और फिर का एक सूत्र (i − 1)वां आदेश।

यह भी देखें

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

संदर्भ

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