https://arolstar52-zhtest.hf.space/index.php?action=history&feed=atom&title=ELEMENTARY 2026-07-10T15:40:18Z 在这个wiki上该页的修订历史 MediaWiki 1.43.9 https://arolstar52-zhtest.hf.space/index.php?title=ELEMENTARY&diff=877130&oldid=prev 2013-03-14T04:55:55Z

<p>机器人：移除1个跨语言链接，现在由<a href="/index.php?title=D:&amp;action=edit&amp;redlink=1" class="new" title="D:（页面不存在）">维基数据</a>的<a href="/index.php?title=D:q5323278&amp;action=edit&amp;redlink=1" class="new" title="D:q5323278（页面不存在）">d:q5323278</a>提供。</p> <p><b>新页面</b></p><div>在[[計算複雜度理論]]裡面，[[複雜度類]]&#039;&#039;&#039;ELEMENTARY&#039;&#039;&#039;是所有[[指數譜系]]裡面的複雜度類聯集：<br /> <br /> : &lt;math&gt; \begin{matrix}<br /> \mathrm{ELEMENTARY} &amp; = &amp; \mathrm{EXP}\cup\mathrm{2EXP}\cup\mathrm{3EXP}\cup\cdots \\<br /> &amp; = &amp; \mathrm{DTIME}(2^{n})\cup\mathrm{DTIME}(2^{2^{n}})\cup<br /> \mathrm{DTIME}(2^{2^{2^{n}}})\cup\cdots<br /> \end{matrix}<br /> &lt;/math&gt;<br /> <br /> 這名稱最早是為了探討[[可計算函數]]和[[不可判定問題]]，由[[László Kalmár]]所提出；most problems in it are far from elementary。Some natural recursive problems lie outside ELEMENTARY, and are thus [[NONELEMENTARY]]。相當值得注意的，有一些[[原始遞歸函數]]問題不在ELEMENTARY內。我們已知：<br /> <br /> LOWER-ELEMENTARY &lt;math&gt;\subsetneq&lt;/math&gt; [[EXPTIME]] &lt;math&gt;\subsetneq&lt;/math&gt; ELEMENTARY &lt;math&gt;\subsetneq&lt;/math&gt; [[PR (complexity)|PR]]<br /> <br /> 與ELEMENTARY僅包含有限的[[冪]]（例如，&lt;math&gt;O(2^{2^n})&lt;/math&gt;）比較，[[PR (複雜度)|PR]]使用的 [[超運算]]更一般化（例如，[[tetration]]），因此PR不包含於ELEMENTARY。<br /> &lt;!--<br /> == 定義 ==<br /> <br /> The definitions of elementary recursive functions are the same as for [[原始遞歸函數]]s, except that primitive recursion is replaced by bounded summation and bounded product. All functions work over the natural numbers. The basic functions, all of them elementary recursive, are:<br /> <br /> # &#039;&#039;&#039;Zero function&#039;&#039;&#039;. Returns zero: &#039;&#039;f&#039;&#039;(x) = 0.<br /> # &#039;&#039;&#039;Successor function&#039;&#039;&#039;: &#039;&#039;f&#039;&#039;(&#039;&#039;x&#039;&#039;) = &#039;&#039;x&#039;&#039; + 1. Often this is denoted by &#039;&#039;S&#039;&#039;, as in &#039;&#039;S&#039;&#039;(&#039;&#039;x&#039;&#039;). Via repeated application of a successor function, one can achieve addition.<br /> # &#039;&#039;&#039;Projection functions&#039;&#039;&#039;: these are used for ignoring arguments. For example, &#039;&#039;f&#039;&#039;(&#039;&#039;a&#039;&#039;, &#039;&#039;b&#039;&#039;) = &#039;&#039;a&#039;&#039; is a projection function.<br /> # &#039;&#039;&#039;Subtraction function&#039;&#039;&#039;: &#039;&#039;f&#039;&#039;(&#039;&#039;x&#039;&#039;, &#039;&#039;y&#039;&#039;) = &#039;&#039;x&#039;&#039; - &#039;&#039;y&#039;&#039; if &#039;&#039;y&#039;&#039; &lt; &#039;&#039;x&#039;&#039;, or 0 if &#039;&#039;y&#039;&#039; &amp;ge; &#039;&#039;x&#039;&#039;. This function is used to define conditionals and iteration.<br /> <br /> From these basic functions, we can build other elementary recursive functions.<br /> <br /> # &#039;&#039;&#039;Composition&#039;&#039;&#039;: applying values from some elementary recursive function as an argument to another elementary recursive function. In &#039;&#039;f&#039;&#039;(&#039;&#039;x&#039;&#039;&lt;sub&gt;1&lt;/sub&gt;, ..., &#039;&#039;x&#039;&#039;&lt;sub&gt;n&lt;/sub&gt;) = &#039;&#039;h&#039;&#039;(&#039;&#039;g&#039;&#039;&lt;sub&gt;1&lt;/sub&gt;(&#039;&#039;x&#039;&#039;&lt;sub&gt;1&lt;/sub&gt;, ..., &#039;&#039;x&#039;&#039;&lt;sub&gt;n&lt;/sub&gt;), ..., &#039;&#039;g&#039;&#039;&lt;sub&gt;m&lt;/sub&gt;(&#039;&#039;x&#039;&#039;&lt;sub&gt;1&lt;/sub&gt;, ..., &#039;&#039;x&#039;&#039;&lt;sub&gt;n&lt;/sub&gt;)) is elementary recursive if &#039;&#039;h&#039;&#039; is elementary recursive and each &#039;&#039;g&#039;&#039;&lt;sub&gt;i&lt;/sub&gt; is elementary recursive.<br /> # &#039;&#039;&#039;Bounded summation&#039;&#039;&#039;: &lt;math&gt;f(m, x_1, \ldots, x_n) = \sum\limits_{i=0}^mg(i, x_1, \ldots, x_n)&lt;/math&gt; is elementary recursive if &#039;&#039;g&#039;&#039; is elementary recursive.<br /> # &#039;&#039;&#039;Bounded product&#039;&#039;&#039;: &lt;math&gt;f(m, x_1, \ldots, x_n) = \prod\limits_{i=0}^mg(i, x_1, \ldots, x_n)&lt;/math&gt; is elementary recursive if &#039;&#039;g&#039;&#039; is elementary recursive.<br /> --&gt;<br /> <br /> {{ComplexityClasses}}<br /> <br /> [[Category:複雜度類]]</div>

imported>Addbot