О генерической сложности проблем 3-раскраски графов Full article
| Journal |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||
|---|---|---|---|
| Output data | Year: 2025, Number: 69, Pages: 121-128 Pages count : 8 DOI: 10.17223/20710410/69/8 | ||
| Tags | генерическая сложность, 3-раскраска графа. | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 25-11-20023 |
Abstract:
Изучается генерическая сложность двух вариантов проблемы о 3-раскраске графов: проблема распознавания и проблема поиска
3-раскраски графа. Для обеих проблем эффективных полиномиальных алгоритмов неизвестно. Проблема поиска 3
-раскраски используется в известном криптографическом протоколе Блюма для доказательства с нулевым разглашением. Предлагается полиномиальный генерический алгоритм для проблемы распознавания 3-раскраски графа. Для проблемы поиска
3-раскраски доказывается, что если P≠NP и P=BPP, то существует подпроблема этой проблемы, для которой нет полиномиального генерического алгоритма. Полученный результат является теоретическим обоснованием применения проблемы поиска 3-раскраски графа в криптографии, где нужно, чтобы проблема взлома криптоалгоритма была трудной для почти всех входов.
Cite:
Рыбалов А.Н.
, Рузанова Д.П.
О генерической сложности проблем 3-раскраски графов
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2025. №69. С.121-128. DOI: 10.17223/20710410/69/8 РИНЦ OpenAlex
О генерической сложности проблем 3-раскраски графов
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2025. №69. С.121-128. DOI: 10.17223/20710410/69/8 РИНЦ OpenAlex
Dates:
| Submitted: | Mar 1, 2025 |
| Accepted: | May 15, 2025 |
| Published print: | Sep 1, 2025 |
| Published online: | Sep 1, 2025 |
Identifiers:
| Elibrary: | 83025883 |
| OpenAlex: | W4415667321 |
Citing:
Пока нет цитирований