- Для задачи о сложности вычисления одночлена от нескольких переменных (задача Беллмана) и для задачи о сложности вычисления набора степеней одной переменной (задача Кнута) при слабых ограничениях в области изменения параметров получены асимптотически точные решения.
- Установлена общая нижняя оценка сложности вычисления систем одночленов, систем целочисленных линейных форм и систем элементов свободных абелевых групп.
- Предложен метод получения верхних оценок сложности систем одночленов, основанный на использовании усиленной модели вычислений с последующим сведением без асимптотического увеличения сложности к исходной модели. На основе этого метода получены асимптотически точные верхние оценки сложности: системы из двух одночленов от нескольких переменных, системы из нескольких одночленов от двух переменных; системы из трех одночленов от трех переменных.
- Для любых фиксированных (или слаборастущих) значениях р и q установлена асимптотика роста сложности вычисления системы из р целочисленных линейных форм от q переменных.
- Получены асимптотически точные верхние оценки сложности вычисления: системы из двух элементов свободной абелевой группы; системы из трех элементов свободной абелевой группы с двумя образующими.
- С использованием полученных оценок сложности вычисления наборов степеней установлена асимптотика роста сложности вычисления двоичных слов с заданным числом (или долей) единиц схемами конкатенации.
- Выявлены новые эффекты в задачах о сложности вычисления систем одночленов, систем целочисленных линейных форм и систем элементов свободных абелевых групп; в частности, установлены принципиальные различия в асимптотическом поведении трех исследуемых мер сложности.
2.Кочергин В. В. О вычислении наборов степеней // Дискретная ма-тематика. — Т. 6, вып. 2. — 1994. — С. 129-137.
3.Кочергин В. В. О сложности вычислений одночленов и наборов сте-пеней // Дискретный анализ. — Новосибирск: Издательство Института математики СО РАН, 1994. — (Тр./РАН. Сиб. отделение. Ин-т математи¬ки; Т. 27) — С. 94-107.
4.Кочергин В. В. О сложности вычислений в конечных абелевых, ниль-потентных и разрешимых группах // Дискретная математика. — Т. 5, вып. 1. — 1993. — С. 91-111.
5.Кочергин В. В. О сложности вычислений в конечных нильпотентных группах // Дискретный анализ и исследование операций. — 1996. — Т. 3, № 1. — С. 43-51.
6.Кочергин В. В. О сложности вычисления систем одночленов с огра-ничениями на степени переменных // Дискретная математика. — Т. 10, вып. 3. — 1998. — С. 27-34.
7.Кочергин В. В. О мультипликативной сложности двоичных слов с заданным числом единиц // Математические вопросы кибернетики, вып. 8. — М.: Наука, 1999. — С. 63-76.
8.Кочергин В. В. О сложности вычисления пары одночленов от двух переменных // Дискретная математика. — Т. 17, вып. 4. — 2005. — С. 116-142.
9.Кочергин В. В. Об асимптотике сложности аддитивных вычислений систем целочисленных линейных форм // Дискретный анализ и исследо¬вание операций. Серия 1. — 2006. — Т. 13, № 2. — С. 38-58.
10.Кочергин В. В. О сложности вычисления системы из трех одно¬ членов от трех переменных // Математические вопросы кибернетики, вып. 15. — М.: Физматлит, 2006. — С. 79-155.
11.Кочергин В. В. О максимальной сложности совместного вычисления систем элементов свободной абелевой группы // Вестник Московского университета. Сер. 1. Математика. Механика. — 2007, № 3. — С. 14-19.
СПИСОК РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ, ОПУБЛИКОВАННЫХ В ИЗДАНИЯХ, НЕ ВХОДЯЩИХ В ПЕРЕЧЕНЬ ВАК
12.Кочергин В. В. Об одном классе аддитивных цепочек // Теоре-тические и прикладные аспекты математических исследований {сборник трудов конференции молодых ученых механико-математического ф-та МГУ). — Москва: Изд-во Московского университета, 1994. — С. 9-13.
13.Кочергин В. В. О сложности некоторых мультипликативных вычи-слений // Материалы YII межгосударственной школы-семинар а "Синтез и сложность управляющих систем" [Минск, 13-16/XI 1995). — Москва: Изд-во механико-математического факультета МГУ, 1996. — С. 16-18.
14.Kochergin V. V. Some generalizations of addition chains problem // Proceedings of two joint French-Russian seminars on combinatorial and algo-rithmical properties of discrete structures [April 1998, Moscow — February 1999, Nansy, France). Project No 8/97. — French-Russian A. M. Liapunov Institute, 2001. — P. 33-41.
15.Кочергин В. В. О сложности получения двоичных слов с заданным числом единиц схемами конкатенации j j Труды III Международной конфе-ренции "Дискретные модели в теории управляющих систем" (22-27 июня 1998 г.). — Москва, Диалог-МГУ, 1998. — С. 58-62.
16.Кочергин В. В. О двух обобщениях задачи об аддитивных це¬почках j j Труды IV Международной конференции "Дискретные модели в теории управляющих систем" (19-25 июня 2000 г.). — Москва, "МАКС Пресс", 2000. — С. 55-59.
17.Кочергин В. В. О сложности вычисления системы одночленов спе-циального вида // Материалы X Межгосударственной школы-семинара "Синтез и сложность управляющих систем" [Минск, 29 ноября- 3 дека¬бря 1999 г.). - М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2000. — С. 12-14.
18.Кочергин В. В. О некоторых обобщениях задачи об аддитив¬ ных цепочках // Дискретная математика и ее приложения. Сборник лекций. — М.: Изд-во Центра прикладных исследований при механико- математическом факультете МГУ, 2001. — С. 59-83.
19.Кочергин В. В. О сложности вычисления систем одночленов от двух переменных // Труды VII Международной конференции «Дискретные мо¬ дели в теории управляющих систем» [Покровское, 4-6 марта 2006 г.). — М.: МАКС Пресс, 2006. — С. 185-190.
20.Кочергин В. В. О сложности совместного вычисления двух элементов свободной абелевой группы // Материалы XVI Международной школы-семинар а «Синтез и сложность управляющих систем» (Санкт-Петербург, 26-30 июня 2006 г.). — М.: Изд-во механико-математического факультета МГУ, 2006. — С. 54-59.
21.Кочергин В. В. Об аддитивной сложности целочисленных матриц размера 3x2// Материалы IX Международного семинара «Дискретная математика и ее приложения», посвященного 75-летию со дня рождения академика О. Б. Лупанова (Москва, 18-23 июня 2007 г.). — М.: Изд-во механико-математического факультета МГУ, 2007. — С. 99-102.
22.Кочергин В. В. О сложности вычисления систем одночленов и си¬стем целочисленных линейных форм // Дискретная математика и ее приложения. Сборник лекций молодежных научных школ по дискретной математике и ее приложениям. Выпуск III. — М.: Изд-во механико-математического факультета МГУ, 2007. — С. 3-63.
23.Кочергин В. В. О сложности совместного вычисления трех элемен¬тов свободной абелевой группы с двумя образующими // Дискретный ана¬лиз и исследование операций. Серия 1. — 2008. — Т. 15, № 2. — С. 23-64.
24.Кочергин В. В. Замечание о сложности вычисления систем од¬ ночленов // Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции (Казань, 2-7 июня 2008 г.). — Казань: Отечество, 2008. — С. 62.