, 
(so, also for 
), in polynomial time and linear space in 
wherein 
and exponential time and exponential space in 
.
В данной работе рассматриваются алгоритмические (вычислимые) вещественные числа и функции, которые представляются функциями Коши, вычислимыми на машине Тьюринга [1] (такая модель алгоритмических чисел и функций называется моделью Ко-Фридмана).
Основные результаты по теории алгоритмических чисел и функций и их вычислительной сложности находятся, например, в [1]; основные результаты по теории вычислительной сложности на машине Тьюринга находятся, например, в [2].
Известно, что вещественная функция Римана 
[3] является полиномиально вычислимой по времени для натуральных 
[4, 5]; алгоритмы из [4, 5] требуют не менее чем 
ячеек памяти для вычисления приближенных значений функции с точностью 
. Также имеется алгоритм вычисления гипергеометрических рядов с произвольной точностью с квази-линейным временем и линейной памятью [6], который применим к вычислению значения 
. Временная и емкостная вычислительная сложность алгоритмов из [4, 5, 6] рассматривается в контексте битовой сложности; на машине Тьюринга алгоритмы из [4, 5] являются полиномиальными по времени и квази-линейными по памяти, а алгоритм из [6] является полиномиальным по вроемени и линейным по памяти.
В данной работе показывается, что вещественная функция Римана является полиномиально вычислимой по времени и линейно вычислимой по памяти (с помощью одного и того же алгоритма) на машине Тьюринга для вещественных , 
, в модели Ко-Фридмана. Для доказательства данного результата строится алгоритм вычисления вещественной функции Римана с полиномиальным временем и линейной памятью на машине Тьюринга. Данный алгоритм основан на разложении функции Римана в числовой ряд [7, 8] для комплексных , 
; в данном алгоритме используются алгоритмы из [9, 10, 11] вычисления вещественной функции 
и гипергеометрических рядов с полиномиальным временем и линейной памятью. Для построения алгоритма вычисления функции Римана используются алгоритм вычисления числовых рядов из [12] и прямой и обратный анализ ошибок округления в численных алгоритмах [9, 10, 11, 13].
Частично результат, изложенный в данной работе, представлялся на научной конференции «Научная дискуссия: вопросы математики, физики, химии, биологии» [14].
1.1 
алгоритмические числа и функции
Функции Коши в модели Ко-Фридмана [1] – это функции, двоично-рационально сходящиеся к вещественным числам. Фукнция 
(здесь 
– множество двоично-рациональных чисел) двоично-рационально сходится к вещественному числу 
, если 
для всех 
; с помощью 
обозначается множество всех функций, двоично-рационально сходящихся к числу .
Definition 1. [1] Вещественное число называется алгоритмическим вещественным число, если содержит функцию 
, вычислимую на машине Тьюринга.
Definition 2. [1] Вещественная функция 
, заданная на отрезке 
, называется алгоритмической вещественнойфункцией на отрезке , если существует машина Тьюринга 
с оракульной функцией такая, что для всех 
и для всех 
функция 
, вычисляемая машиной с оракульной функцией , принадлежит 
.
1.2 Вычислительная сложность алгоритмических функций
Definition 3. [1] Фукнция 
называется 
вычислимой по времени вещественной функцией на отрезке , если для всех алгоритмических вещественных чисел функция 
( берется из определения алгоритмических вещественных функций) является вычислимой по времени.
Definition 4. [1] Функция называется 
вычислимой по памяти вещественной функцией на отрезкеl , если для всех алгоритмических вещественных чисел функция ( берется из определения алгоритмических вещественных функций) является вычислимой по памяти.
Входными данными функций и является запись 
(повторение данного символа 
раз) в случае, когда функции вычисляются с точностью .
С помощью FP//LINSPACE обозначается класс строковых функций, вычислимых за полиномиальное время и линейную память (с помощью одного и того же алгоритма) на машине Тьюринга. Полиномиально вычислимые по времени и линейно вычислимые по памяти алгоритмические вещественные числа и функции называются FP//LINSPACE алгоритмическими вещественными функциями. Множество FP//LINSPACE алгоритмических вещественных функций на отрезке обозначается с помощью FP//LINSPACE
.
1.3 Вычисление приближений вещественных функций
В данной работе используются следующие результаты из [9, 10, 11].
Для умножения 
и 
с точностью , где и – вещественные числа такие, что 
и 
для некоторого натурального числа 
, достаточно вычислять и с точностью 
для 
, где 
– линейная функция натуральных аргументов.
Для вычисления величины, обратной к с точностью , где – вещественное число такое, что 
для некоторого натурального числа , достаточно вычислять с точностью для 
, где 
– линейная функция натуральных аргументов.
Для вычисления функции с точностью , где вещественные 
и вещественное число 
, достаточно вычислять и 
с точностью для 
, где 
– линейная функция натуральных аргументов.
Можно показать, что для вычисления функции с точностью , где вещественные 
и вещественное 
, достаточно вычислять с точностью для 
, где 
– линейная функция натуральных аргументов.
2 FP//LINSPACE вычисление функции
Рассмотрим числовой ряд [7, 8] фунции Римана , сходящийся для всех комплексных чисел (исключая 
для целых ):
(1)
Пусть
и
запишем ряд (1) следующим образом:
(2)
Пусть – натруальное число, 
; пусть 
и – натуральное число такое, что 
. Будем вычислять по формуле (2) с точностью для таких , где – натуральное число.
2.1 Вычисление 
Так как
(3)
выполняютя соотношения
Следовательно
,
где 
– некторая константа (следует из соотношений, изложенных в параграфе 2.2.3).
Это означает, что для вычисления 
по формуле (2) с точностью достаточно вычислять величины 
и 
с точностью 
, где 
(
– константа, зависящая от 
).
Далее, для вычисления величины с точностью воспользуемся алогитмом из [9, 10, 11] вычисления функции с точностью ; при этом достаточно вычислять величину 
до точности 
для 
, где 
– линейная функция натуральных аргументов (
– некоторое натуральное число).
2.2 Вычисление
Будем вычислять функцию следующим образом:
1) вычисляем 
с точностью 
;
2) вычисляем 
с точностью ;
3) вычисляем
,
где 
и 
– приближенные значения величин and соответственно с точностью ; пусть 
– точность вычисления величины 
;
4) вычисляем
пусть 
– точность вычисления величины 
.
Для вычисления величины с точностью воспользуемся алгоритмом из [9, 10, 11] вычисления функции с точностью ; для этого достаточно вычислять величину с точностью 
для 
, где 
– это линейная функция натуральных аргументов (
– натуральное число).
Следовательно, для вычисления величины с точностью с помощью суммирования ряда величину достаточно вычислять с точностью , где 
.
2.2.1 Вычисление
Запишем величину 
следующим образом:
Будем вычислять 
в цикле по 
, на каждом шаге вычисляя
(при этом 
), где 
– приближенное значение величины 
с точностью 
, 
– приближенное значение величины 
с точностью ; 
для всех натуральны 
. Будем вычислять с точностью , отбрасывая все биты после точки, начиная с 
-го бита.
Используя метод математической индукции по , покажем, что 
для каждого , если брать 
.
База индукции: 
; в этом случае, величина 
, равнаяo 
, вычисляется с точностью 
. Индукционный рпереход: пусть 
для 
. В этом случае
(здесь используется оценка 
). Следовательно, выполняется оценка
в частности, 
. Это означает, что достаточно брать 
и для вычисления с точностью 
. И, далее, для вычисления 
с точностью достаточно брать 
где 
– линейная функция натурального аргумента, так как 
.
2.2.2 Вычисление
Будем вычислять 
в цикле по 
. Так как
где 
и 
, выполняется соотношение
Далее, из
следует
Следовательно, если взять 
и вычислять и с точностью , то точность вычисления будет .
Найдем точность вычисления of используя следующие соотношения:
где
и 
Так как
выполняется соотношение
Оценим сверху величину
Пусть 
– нечетное натуральное число и 
; пусть
Так как 
, выполняются равенства
Следовательно,
и 
из чего получаем
и 
(те же самые соотношения выполняются в случае, когда – четное). Следовательно
Как результат, если взять 
, то
Это означает, что достаточно взять 
и для вычисления с точностью .
3 Основной результат
Как результат, получаем, что для вычисления с точностью для 
достаточно выполнить следующие шаги:
1) вычислить с точностью для 
где 
– линейная функция натуральных аргументов, и
2) использовать 
умножений двоично-рациональных чисел длины
, где 
– линейная функция натуральных аргументов.
Следовательно выполняется следующая теорема.
Теорема 1. Вещественная функция Римана принадлежит классу FP//LINSPACE
для любого интервала , где 
, 
, 
и – натуральное число, .
Также выполняется следующая теорема (учитывая параграф 1.3).
Теорема 2. Вещественная функция Римана является экспоненциально вычислимой по времени и экспоненциально вычислимой по памяти по для любого отрезка , где , , и – натуральное число, .
Рецензенты:
Косовский Н.К., д.ф.-м.н., профессор, зав. кафедрой информатики, математико-механический факультет, Санкт-Петербургский государственный университет (Министерство образования и науки Российской Федерации), г. Санкт-Петербург.
Ермаков С.М., д.ф.-м.н., профессор, зав. кафедрой статистического моделирования, математико-механический факультет, Санкт-Петербургский государственный университет (Министерство образования и науки Российской Федерации), г. Санкт-Петербург.