name: Вопросы теории сложности вычислений в алгебраических и логических структурах
keyword_list: Пороговая функция пороговая схема гиперграфовая программа мин-плюс алгебра функция голосования
abstract: Диссертация посвящена исследованию вопросов сложности вычислений в алгебраических и логических структурах. Построена иерархия точных пороговых схем и установлена ее связь с иерархией пороговых схем. Исследованы классы булевых функций, реализуемые знаками многочленов над переменными, принимающими произвольную пару действительных значений. Доказаны оценки на минимальное k, для которого существует монотонная булева схема фиксированной глубины, реализующая функцию голосования от n переменных и состоящая из функций голосования от k переменных. Установлена сложность булевых функций в модели гиперграфовых программ с различными видами ограничений. Получены аналоги комбинаторной теоремы о нулях и леммы Шварца-Зиппеля для мин-плюс многочленов. Доказана полиномиальная эквивалентность задачи о разрешимости мин-плюс линейных систем многочленов и задачи об определении победителя в циклических играх. Доказан аналог теоремы Гильберта о нулях для мин-плюс многочленов.
chairman_dissertation_council.name: Алексей
chairman_dissertation_council.surname: Паршин
chairman_dissertation_council.patronymic: Николаевич
chairman_dissertation_council.position: заведующий отделом алгебры
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Академик
chairman_dissertation_council.wos_research_id: Q-8379-2016
chairman_dissertation_council.scopus_author_id: 7006200324
chairman_dissertation_council.rinc_id: 10742
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Дмитрий
organization_supervisor.surname: Трещев
organization_supervisor.patronymic: Валерьевич
organization_supervisor.position: директор
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.41.41
rubrics.name: Алгоритмы решения задач вычислительной и дискретной математики
rubrics.code: 27.03.45
rubrics.name: Теория вычислимости
oecds.code: 01.01.PN
oecds.name: MATHEMATICS, APPLIED
speciality_codes.name: Математическая логика, алгебра и теория чисел
speciality_codes.code: 01.01.06
opponents.fio: Аблаев Ф.М.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Дискретная математика и математическая кибернетика
opponents.responsible_type: Оппонент
opponents.fio: Волков М.В.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Математическая логика, алгебра и теория чисел
opponents.responsible_type: Оппонент
opponents.fio: Гирш Э.А.
opponents.scientific_degree: Доктор физико-математических наук
opponents.speciality_code: Математическая логика, алгебра и теория чисел
opponents.responsible_type: Оппонент
protection_organization.short_name: МИАН
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ МАТЕМАТИЧЕСКИЙ ИНСТИТУТ ИМ. В.А. СТЕКЛОВА РОССИЙСКОЙ АКАДЕМИИ НАУК
protection_organization.ogrn: 1027739665436
protection_organization.supervisor_name: ДМИТРИЙ
protection_organization.supervisor_surname: ТРЕЩЕВ
protection_organization.supervisor_patronymic: ВАЛЕРЬЕВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные бюджетные учреждения
author_organization.short_name: МИАН
author_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ МАТЕМАТИЧЕСКИЙ ИНСТИТУТ ИМ. В.А. СТЕКЛОВА РОССИЙСКОЙ АКАДЕМИИ НАУК
author_organization.ogrn: 1027739665436
author_organization.supervisor_name: ДМИТРИЙ
author_organization.supervisor_surname: ТРЕЩЕВ
author_organization.supervisor_patronymic: ВАЛЕРЬЕВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Федеральные государственные бюджетные учреждения