- Разработан алгоритм расшифровки функций, заданных на множестве целочисленных точек политопа и обладающих свойством, что множества нулей и единиц каждой такой функции можно описать системами линейных неравенств. При любой фиксированной размерности п и некоторых дополнительных ограничениях алгоритм является полиномиальным от размера линейной системы, описывающей политоп.
- Для пороговых функций, определенных на множестве целочисленных точек политопа, предложен алгоритм расшифровки, при фиксированной размерности полиномиальный от размера задания политопа. Установлена нижняя оценка сложности этой задачи. Оракульная сложность предложенного алгоритма при фиксированном п близка по порядку к нижней оценке сложности.
- Для пороговых функций А-значной логики предложен алгоритм расшифровки, полиномиальный при фиксированном п. Установлена нижняя оценка сложности этой задачи. Оракульная сложность предложенного алгоритма при фиксированном п близка по порядку к нижней оценке сложности.
- Описано строение минимального разрешающего множества пороговой функции А-значной логики. Найдены верхняя и нижняя оценка длины обучения в классе таких функций; при фиксированном п эти оценки совпадают по порядку.
- Разработан алгоритм расшифровки пороговых функций А-значной логики, зависящих от двух переменных. Для этих функций установлен порядок сложности расшифровки, найдены точное значение длины обучения и асимптотическое значение средней мощности минимального разрешающего множества.
- Установлена связь задачи расшифровки пороговой функции двух переменных с проблемой нахождения диофантовых приближений вещественных чисел. Предложен полиномиальный алгоритм приближения вещественного числа, заданного оракулом, и полиномиальный алгоритм приближения алгебраического числа, заданного минимальным многочленом.
- Предлагается новая модификация («графовый» тест проверки смежности экстремальных лучей) метода двойного описания построения вершинного описания полиэдра. Теоретическая оценка сложности построенной модификации и результаты экспериментов показали преимущество алгоритма по сравнению с классическим его вариантом.
2.Золотых Н. Ю. О пороговых и близких к ним функциях, определенных в целочисленных точках политопа // Дискретный анализ и исследование операций. Серия 1. - 1998. - Т. 5, № 2. - С. 40-54.
3.Золотых Н. Ю. Оракульная сложность задачи о рюкзаке // Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Математическое моделирование и оптимальное управление. — 2000. — № 1. — С. 84-87.
4.Золотых Н. Ю. Пороговые функции, зависящие от двух переменных: сложность расшифровки и мощность разрешающего множества // Материалы четвертой молодежной научной школы по дискретной математике и ее приложениям. — М.: Издательство механико-матем. факультета МГУ, 2000. — С. 48-54.
5.Золотых Н. Ю. О сложности расшифровки пороговых функций, зависящих от двух переменных // Материалы XI Межгосударственной школы-семинара «Синтез и сложность управляющих систем». Часть I. — М.: Издательство Центра прикладных исследований при механико-математическом ф-те МГУ, 2001. - С. 74-79.
6.Золотых Н. Ю. О сложности решения одного класса задач целочисленного линейного программирования // Дискретный анализ и исследование операций. Серия 2. - 2003. - Т. 10, № 1. - С. 3-10.
7.Золотых Н. Ю. Оценки мощности минимального разрешающего множества пороговой функции многозначной логики // Математические вопросы кибернетики. Вып. 17. — М.: Физматлит, 2008. — С. 159-168.
8.Золотых Н. Ю. Новая модификация метода двойного описания для построения остова многогранного конуса // Журнал вычислительной математики и математической физики. — 2012. — Т. 52, № 1. — С. 153-163.
9.Золотых Н. Ю. Расшифровка пороговой функции, заданной расширенным оракулом // Вестник Нижегородского университета им. Н.И. Лобачевского. - 2012. - № 3. - С. 175-178.
10.Золотых Н. Ю., Чирков А. Ю. О верхней оценке мощности минимального разрешающего множества пороговой функции // Дискретный анализ и исследование операций. — 2012. — Т. 19, № 5. — С. 35-46.
11.Золотых Н. Ю., Чирков А. Ю. Сложность расшифровки пороговых функций многозначной логики // Материалы XI Международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О. Б. Лупанова (18—23 июня 2012 г.). — М.: Издательство механико-матем. факультета МГУ, 2012. — С. 63-77.
12.Золотых Н. Ю., Шевченко В. Н. Расшифровка пороговых функций А-значной логики // Дискретный анализ и исследование операций. — 1995.-Т. 2, №3.-С. 18-23.
13.Золотых Н. Ю., Шевченко В. Н. Расшифровка пороговых функций и диофантовы приближения // Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Математическое моделирование и оптимальное управление. — 1998. — № 1. — С. 199-207.
14.Золотых Н. Ю., Шевченко В. Н. Об оценке сложности расшифровки пороговых функций А-значной логики // Журнал вычислительной математики и математической физики. — 1999. — Т. 39, № 2. — С. 346-352.
15.Шевченко В. Н., Золотых Н. Ю. О сложности расшифровки пороговых функций А-значной логики // Доклады РАН.— 1998.— Т. 362, № 5.— С. 606-608.
16.Shevchenko V. N, Zolotykh N. Y. Decoding of threshold functions defined on the integer points of a polytope // Pattern recognition and image analysis. — 1997. - V. 7, N. 2. - P. 235-240.
17.Shevchenko V. N., Zolotykh N. Y. Lower bounds for the complexity of learning half-spaces with membership queries // Lecture Notes in Computer Science. V. 1501. - Springer-Verlag, 1998. - P. 61-71.