ЭЛЕМЕНТАРНЫЙ

Чтобы узнать о других значениях, см. «Элементарный» .

В теории сложности вычислений класс сложности ЭЛЕМЕНТАРНЫЙ элементарных рекурсивных функций представляет собой объединение классов

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

Название было придумано Ласло Кальмаром в контексте рекурсивных функций и неразрешимости ; большинство задач в нем далеко не элементарны. Некоторые задачи естественной рекурсии лежат за пределами ELEMENTARY и, следовательно, являются NONELEMENTARY . В частности, существуют примитивно-рекурсивные задачи, которых нет в ELEMENTARY. Мы знаем

НИЖНЕЭЛЕМЕНТАРНЫЙ ⊊ EXPTIME ⊊ ЭЛЕМЕНТАРНЫЙ ⊊ PR ⊊ R

В то время как ELEMENTARY содержит ограниченные применения возведения в степень (например, $O(2^{2^{n}})$), PR допускает более общие гипероператоры (например, тетрацию ), которые не содержатся в ELEMENTARY.

Определение

Определения элементарных рекурсивных функций такие же, как и для примитивно-рекурсивных функций , за исключением того, что примитивная рекурсия заменена ограниченным суммированием и ограниченным произведением. Все функции работают с натуральными числами . Основные функции, все элементарно рекурсивные:

1. Нулевая функция . Возвращает ноль: f (x) = 0.
2. Функция-преемник : f ( x ) = x + 1. Часто это обозначается S , как в S ( x ). Путем многократного применения функции-преемника можно добиться сложения.
3. Функции проекции : они используются для игнорирования аргументов. Например, f ( a , b ) = a — проекционная функция.
4. Функция вычитания : ж ( Икс , y ) знак равно Икс - y, если y < Икс , или 0, если y ≥ Икс . Эта функция используется для определения условий и итерации.

Из этих базовых функций мы можем построить другие элементарные рекурсивные функции.

1. Композиция : применение значений некоторой элементарной рекурсивной функции в качестве аргумента к другой элементарной рекурсивной функции. В f ( x ₁ , ..., x _n ) = h ( g ₁ ( x ₁ , ..., x _n ), ..., g _m ( x ₁ , ..., x _n )) элементарно если h элементарно рекурсивно и каждое gi _{рекурсивно ,} элементарно рекурсивно.
2. Ограниченное суммирование : $f(m,x_{1},\ldots ,x_{n})=\sum \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})$ элементарно рекурсивно, если g элементарно рекурсивно.
3. Ограниченный продукт : $f(m,x_{1},\ldots ,x_{n})=\prod \limits _{i=0}^{m}g(i,x_{1},\ldots ,x_{n})$ элементарно рекурсивно, если g элементарно рекурсивно.

Основа ЭЛЕМЕНТАРНОГО

Класс элементарных функций совпадает с замыканием по композиции проекторов и одним из следующих наборов функций: $\{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$ представляет собой побитовое И для n и m .

Описательная характеристика

По описательной сложности ЭЛЕМЕНТАРНЫЙ равен классу НО языков , которые можно описать формулой логики высшего порядка . Это означает, что каждый язык в классе ЭЛЕМЕНТАРНОЙ сложности соответствует формуле более высокого порядка, которая верна и только для элементов языка. Точнее, ${\mathsf {NTIME}}\left(2^{2^{\cdots {2^{O(n)}}}}\right)=\exists {}{\mathsf {HO}}^{i}$, где ⋯ обозначает башню из i возведений в степень и $\exists {}{\mathsf {HO}}^{i}$ — это класс запросов, которые начинаются с кванторов существования i -го порядка, а затем с формулы ( i − 1) -го порядка.

См. также

• Элементарная арифметика функций
• Примитивная рекурсивная функция
• Иерарх Гжегорчик
• ВРЕМЯ ЭКСПРЕСС

Ссылки

• Роуз, HE, Субрекурсия: функции и иерархии , Oxford University Press , 1984. ISBN   0-19-853189-3