Изучается генерическая сложность проблемы распознавания гамильтоновых путей в конечных графах. Путь в графе называется гамильтоновым, если он проходит через все вершины ровно по одному разу. Доказывается, что при условии P ≠ NP и P = BPP для этой проблемы не существует полиномиального сильно генерического алгоритма.
Скачать электронную версию публикации
Загружен, раз: 41
- Title О генерической сложности проблемы распознавания гамильтоновых путей
- Headline О генерической сложности проблемы распознавания гамильтоновых путей
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 53
- Date:
- DOI 10.17223/20710410/53/8
Ключевые слова
генерическая сложность, гамильтонов путьАвторы
Ссылки
Karp R. Reducibility among combinatorial problems // R. E. Miller and J. W. Thather (eds.). Complexity of Computer Computations. The IBM Research Symposia Ser., 1972. P.85-103.
Impagliazzo R. and Wigderson A. P = BPP unless E has subexponential circuits: Derandomizing the XOR Lemma // Proc. 29th STOC. El Paso: ACM, 1997. P.220-229.
Kapovich I., 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.
Гимади Э.К., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. 1975. Т. 31. С. 35-42.
Рыбалов А. О генерической сложности проблемы общезначимости булевых формул // Прикладная дискретная математика. 2016. №2(32). С. 119-126.
Перепелица В.А. О двух задачах из теории графов // Докл. АН СССР. 1970. Т. 194. №6. С.1269-1272.
Posa L. Hamiltonian circuits in random graphs // Discrete Math. 1976. V. 14. P. 359-364.
О генерической сложности проблемы распознавания гамильтоновых путей | Прикладная дискретная математика. 2021. № 53. DOI: 10.17223/20710410/53/8
Скачать полнотекстовую версию
Загружен, раз: 106