|
Записки научных семинаров ПОМИ, 2016, том 448, страницы 80–95
(Mi znsl6304)
|
|
|
|
Вычислительная сложность задачи Коши для задачи трёх тел
Н. Н. Васильевab, Д. А. Павловc a Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН, С.-Петербург, Россия
b С.-Петербургский государственный электротехнический университет, С.-Петербург, Россия
c Институт прикладной астрономии, наб. Кутузова 10, С. Петербург, Россия
Аннотация:
Статья посвящена анализу вычислительной сложности задачи Коши для систем ОДУ. Вводится формальная постановка такой задачи, использующая машину Тьюринга и оракула для записи вещественных входных данных. Доказывается отсутствие полиномиальных верхних оценок сложности решения задачи Коши для проблемы трех тел. Доказательство использует осциллирующие решения задачи Ситникова, имеющие сложное динамическое поведение, являющееся препятствием к наличию алгоритма, вычисляющего решение в конечной точке за полиномиальное время. Библ. – 15 назв.
Ключевые слова:
сложность алгоритма, машина Тьюринга, задача Коши, задача трех тел, осциллирующие траектории.
Поступило: 17.10.2016
Образец цитирования:
Н. Н. Васильев, Д. А. Павлов, “Вычислительная сложность задачи Коши для задачи трёх тел”, Теория представлений, динамические системы, комбинаторные методы. XXVII, Зап. научн. сем. ПОМИ, 448, ПОМИ, СПб., 2016, 80–95; J. Math. Sci. (N. Y.), 224:2 (2017), 221–230
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl6304 https://www.mathnet.ru/rus/znsl/v448/p80
|
Статистика просмотров: |
Страница аннотации: | 216 | PDF полного текста: | 71 | Список литературы: | 36 |
|