Search
  • Papers


Вычислительная сложность задачи Коши для задачи трёх тел

Authors: Н. Н. Васильев, Pavlov D.

Journal: Записки научных семинаров ПОМИ Том 448, 80-95

Year: 2016

Full text

About the paper

Keywords: сложность алгоритма, машина Тьюринга, задача Коши, задача трех тел, осциллирующие траектории, computational complexity, Turing machine, initial value problem, three-body problem, oscillatory motion

Статья посвящена анализу вычислительной сложности задачи Коши для систем ОДУ. Вводится формальная постановка такой задачи, использующая машину Тьюринга и оракула для записи вещественных входных данных. Доказывается отсутствие полиномиальных верхних оценок сложности решения задачи Коши для проблемы трех тел. Доказательство использует осциллирующие решения задачи Ситникова, имеющие сложное динамическое поведение, являющееся препятствием к наличию алгоритма, вычисляющего решение в конечной точке за полиномиальное время.