RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Семинар отдела математической логики «Алгоритмические вопросы алгебры и логики»
15 мая 2012 г. 18:30–20:05, г. Москва, ГЗ МГУ, ауд. 16-04
 


Об уравнениях в алгебраической системе $(\mathbb Z,\min, +)$

В. В. Подольский

Количество просмотров:
Эта страница:104

Аннотация: В докладе будет рассматриваться так называемое мин-плюс полукольцо $(\mathbb Z,\oplus,\otimes)$, где $x \oplus y = \min(x,y)$ и $x \otimes y = x+y$. Мы будем рассматривать уравнения двух типов над этим полукольцом: односторонние и двухсторонние линейные мин-плюс уравнения. Односторонним линейным мин-плюс уравнением мы в рамках этого доклада будем называть выражение вида $(a_1 \otimes x_1) \oplus \ldots \oplus (a_n \otimes x_n)$. Вектор $(x_1, \ldots, x_n)$ является решением такого уравнения, если минимум $\min_i(a_i + x_i)$ достигается дважды. Двухсторонние линейные мин-плюс уравнения – это уравнения вида $(a_1 \otimes x_1) \oplus \ldots \oplus (a_n \otimes x_n) = (b_1 \otimes x_1) \oplus \ldots \oplus (b_n \otimes x_n)$.
В докладе мы рассматриваем алгоритмические вопросы связанные с системами двухсторонних и односторонних линейных мин-плюс уравнений. В частности, показано, что проблема распознавания разрешимости односторонних систем мин-плюс уравнений эквивалентна задаче об определении победителя в циклических играх – известной задаче из $\mathrm{NP} \cap \mathrm{coNP}$ (для двухсторонних систем аналогичный результат был известен ранее). Кроме того, доказано, что задача распознавания равносильности двух данных систем также эквивалентна задаче о циклических играх, а значит также лежит в $\mathrm{NP} \cap \mathrm{coNP}$. Этот результат доказан как для односторонних, так и для двухсторонних систем. Также доказано, что задача вычисления размерности пространства решений линейной мин-плюс системы (вновь, как односторонней, так и двухсторонней) $\mathrm{NP}$-полна.
Доклад основан на совместной работе с Д. Ю. Григорьевым.

Website: http://arxiv.org/abs/1204.4578

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018