Страница публикации
О скрытых упрощающих структурах в комбинаторных задачах и их вероятностных обобщениях
Тип публикации: Статья в журнале
Тип материала: Текст
Авторы: Семёнов А.А.
Журнал: Прикладная дискретная математика. Приложение
Язык публикации: russian
Номера страниц: 100-104
Количество страниц: 5
Номер: 15
Год публикации: 2022
Отчетный год: 2022
Аннотация: Дан обзор некоторых недавних результатов, связанных со структурами, за которыми в англоязычной литературе закрепился термин “Backdoor”. Наиболее близким аналогом в русском, по-видимому, является термин «лазейка». Лазейка - это такое множество переменных в произвольной задаче удовлетворения ограничений, знание которого существенно упрощает рассматриваемую задачу либо даёт верхнюю оценку трудности её решения, которая лучше трудности тривиальной переборной стратегии. Лазейки в последние годы являются популярным объектом исследований как в прикладных областях, так и в теоретических (главным образом, в параметризованной сложности). Обсуждается применение лазеек для повышения эффективности решения конкретных комбинаторных задач из семейств SAT (проблема булевой выполнимости) и 0-1-ILP (0-1-целочисленное линейное программирование).
Индексируется WOS: Нет
Индексируется Scopus: Нет
Индексируется УБС: Нет
Индексируется РИНЦ: Да
Индексируется ВАК: Нет
Индексируется CORE: Нет
Export Citations