प्राथमिक

For अन्य अर्थ, see प्राथमिक.

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

${\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 (जटिलता) अधिक सामान्य हाइपर ऑपरेटरों (उदाहरण के लिए टेट्रेशन) की अनुमति देता है जो प्राथमिक में सम्मिलित नहीं हैं।

परिभाषा

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

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 यदि y ≥ x इस कार्य का उपयोग नियमबद्ध और पुनरावृत्ति को परिभाषित करने के लिए किया जाता है।

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

1. संरचना: कुछ प्राथमिक पुनरावर्ती कार्य से मानो को दूसरे प्राथमिक पुनरावर्ती कार्य के तर्क के रूप में प्रयुक्त करना। f(x₁, ..., x_n) = h(g₁(x₁, ..., x_n), ..., g_m(x₁, ..., x_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$\,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 है.

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

1. संरचना: कुछ प्राथमिक पुनरावर्ती कार्य से मानो को दूसरे

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

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

यह भी देखें

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

संदर्भ

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