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

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





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








Семинар отдела дискретной математики МИАН
24 октября 2006 г., г. Москва, МИАН, комн. 511 (ул. Губкина, 8)
 


О сложности решения систем булевых уравнений

С. П. Горшков

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

Аннотация: Рассматриваются классы систем булевых уравнений без ограничений на выбор неизвестных (классы вида $[F]_{NC}$). Известна теорема разделимости Т. Шефера (Т. Schaefer, 1978) о том, что задача распознавания совместности систем таких классов является либо полиномиальной, либо NP-полной, и это определяется шестью свойствами порождающего набора булевых функций $F$.
В докладе будут представлены дальнейшие исследования сложности решения систем рассматриваемых классов. Доказаны теорема разделимости для задачи распознавания совместности систем классов $[F]_{NC}$ при исключении тривиальных решений и теорема разделимости для задачи определения числа решений систем классов $[F]_{NC}$. Значительное место в докладе будет уделено изучению множеств булевых функций, порождающих полиномиально решаемые классы систем булевых уравнений без ограничений на выбор неизвестных.

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