Изучается генерическая сложность двух вариантов проблемы о 3-раскраске графов: проблема распознавания и проблема поиска 3-раскраски графа. Для обеих проблем эффективных полиномиальных алгоритмов неизвестно. Проблема поиска 3-раскраски используется в известном криптографическом протоколе Блюма для доказательства с нулевым разглашением. Предлагается полиномиальный генерический алгоритм для проблемы распознавания 3-раскраски графа. Для проблемы поиска 3-раскраски доказывается, что если Р = NP и Р = ВРР, то существует подпроблема этой проблемы, для которой нет полиномиального генерического алгоритма. Полученный результат является теоретическим обоснованием применения проблемы поиска 3-раскраски графа в криптографии, где нужно, чтобы проблема взлома криптоалгоритма была трудной для почти всех входов.
- Title О генерической сложности проблем 3-раскраски графов
- Headline О генерической сложности проблем 3-раскраски графов
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 69
- Date:
- DOI 10.17223/20710410/69/8
Ключевые слова
генерическая сложность, 3-раскраска графаАвторы
Ссылки
Karp R. Reducibilitv among combinatorial problems // R. E. Miller, J. W. Thatcher, and J.D. Bohlinger (eds).Complexity of Computer Computations. The IBM Research Symposia Series. Boston: Springer, 1972. P.85-103.
Blum M. How to prove a theorem so no one else can claim it // Proc. ICM’86. AMS, 1986. P. 1444-1451.
Goldreich O., Micali S., and Wigderson A. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems // Proc. SFCS’86. IEEE Computer Society, 1986. P. 174-187.
Kapovich L., Miasnikov A., Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. V. 264. No. 2. P. 665-694.
Рыбалов A. H. О генерической сложности проблемы распознавания квадратичных вычетов // Прикладная дискретная математика. 2015. №2 (28). С. 54-58.
Рыбалов А. Н. О генерической сложности проблемы дискретного логарифма // Прикладная дискретная математика. 2016. УЗ (33). С.93-97.
Рыбалов А. Н. О генерической сложности проблемы извлечения корня в группах вычетов // Прикладная дискретная математика. 2017. У 38. С. 95-100.
Impagliazzo R. and Wigderson А. р = ВРР unless Е has subexponential circuits: Derandomizing the XOR Lemma. Proc. 29th STOC. El Paso: ACM, 1997. P. 220-229.
Катаев А., Шень А., Вялый M. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо. 1999. 192 с.
О генерической сложности проблем 3-раскраски графов | Прикладная дискретная математика. 2025. № 69. DOI: 10.17223/20710410/69/8
Скачать полнотекстовую версию
Загружен, раз: 56