|
Дискретный анализ и исследование операций, 2009, том 16, выпуск 2, страницы 42–60
(Mi da567)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
О классе функций, элементарных по Сколему
С. А. Волков Московский государственный университет им. М. В. Ломоносова, Москва, Россия
Аннотация:
Рассматриваются различные эквивалентные определения класса функций, элементарных по Сколему (аналогичные известным для класса функций, элементарных по Кальмару), и некоторые результаты, связанные с этим классом, полученные различными математиками. Некоторые определения данного класса исследовались математиками независимо друг от друга, и в работе доказана их эквивалентность. Исследуется вопрос о наличии в этом классе конечных базисов по суперпозиции. Доказывается, что проблема наличия таких базисов эквивалентна известной проблеме из теории сложности вычислений. Библиогр. 26.
Ключевые слова:
классификация рекурсивных функций, вычислительная сложность.
Статья поступила: 24.10.2008
Образец цитирования:
С. А. Волков, “О классе функций, элементарных по Сколему”, Дискретн. анализ и исслед. опер., 16:2 (2009), 42–60; J. Appl. Industr. Math., 4:4 (2010), 588–599
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da567 https://www.mathnet.ru/rus/da/v16/i2/p42
|
Статистика просмотров: |
Страница аннотации: | 440 | PDF полного текста: | 143 | Список литературы: | 45 | Первая страница: | 7 |
|