О генерической сложности проблем 3-раскраски графов | Sciact - Система учета научной деятельности ИМ СО РАН

О генерической сложности проблем 3-раскраски графов Научная публикация

Журнал

Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263

Вых. Данные

Год: 2025, Номер: 69, Страницы: 121-128 Страниц : 8 DOI: 10.17223/20710410/69/8

Ключевые слова

генерическая сложность, 3-раскраска графа.

Авторы

Рыбалов А.Н. ¹ , Рузанова Д.П. ¹

Организации

1	Институт математики им. С.Л.Соболева СО РАН

Информация о финансировании (1)

Российский научный фонд

25-11-20023

Изучается генерическая сложность двух вариантов проблемы о 3-раскраске графов: проблема распознавания и проблема поиска 3-раскраски графа. Для обеих проблем эффективных полиномиальных алгоритмов неизвестно. Проблема поиска 3 -раскраски используется в известном криптографическом протоколе Блюма для доказательства с нулевым разглашением. Предлагается полиномиальный генерический алгоритм для проблемы распознавания 3-раскраски графа. Для проблемы поиска 3-раскраски доказывается, что если P≠NP и P=BPP, то существует подпроблема этой проблемы, для которой нет полиномиального генерического алгоритма. Полученный результат является теоретическим обоснованием применения проблемы поиска 3-раскраски графа в криптографии, где нужно, чтобы проблема взлома криптоалгоритма была трудной для почти всех входов.

Рыбалов А.Н. , Рузанова Д.П.
О генерической сложности проблем 3-раскраски графов
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2025. №69. С.121-128. DOI: 10.17223/20710410/69/8 РИНЦ OpenAlex

Поступила в редакцию:	1 мар. 2025 г.
Принята к публикации:	15 мая 2025 г.
Опубликована в печати:	1 сент. 2025 г.
Опубликована online:	1 сент. 2025 г.

РИНЦ:	83025883
OpenAlex:	W4415667321

Пока нет цитирований