ГлавнаяАрхивО генерической сложности проблемы разбиения графа на треугольники

О генерической сложности проблемы разбиения графа на треугольники | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/10

NP-полнота проблемы разбиения графа на треугольники доказана Шейфером в 1974 г. и содержится в классической монографии М. Гэри и Д. Джонсона. В данной работе изучается генерическая сложность этой проблемы. Доказывается, что при условии P ≠ NP и P = BPP для её решения не существует полиномиального сильно генерического алгоритма.
  • Title О генерической сложности проблемы разбиения графа на треугольники
  • Headline О генерической сложности проблемы разбиения графа на треугольники
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 58
  • Date:
  • DOI 10.17223/20710410/58/10
Ключевые слова
генерическая сложность, разбиение графа на треугольники
Авторы
Ссылки
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 420с.
Kapovichl., 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.
Гимади Э. X., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. 1975. Т. 31. С. 35-42.
Blum M. How to prove a theorem so no one else can claim it // Proc.Intern. Congress Math., Berkeley, CA, 1986. P.1444-1451.
Myasnikov A. G. and Rybalov A. N. Generic complexity of undecidable problems //j. Symbolic Logic. 2008. V. 73. No. 2. P.656-673.
Rybalov A. N. On the strongly generic undecidability of the Halting Problem // Theor.Comput. Sci. 2007. V.377. P.268-270.
Rybalov A. N. Generic complexity of Presburger arithmetic // Theory Comput. Systems. 2010. V. 46. No. 1. P.2-8.
Rybalov A. N. Generic complexity of the Diophantine problem // Groups Complexity Cryptology. 2013. V. 5. No. 1. P. 25-30.
Rybalov A. N. Generic hardness of the Boolean satisfiability problem // Groups Complexity Cryptology. 2017. V. 9. No. 2. P.151-154.
Рыбалов А. Н. О генерической сложности проблемы кластеризации графов // Прикладная дискретная математика. 2019. №46. С. 72-77.
Рыбалов А. Н. О генерической сложности проблемы распознавания гамильтоновых путей // Прикладная дискретная математика. 2021. №53. С. 120-126.
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.
Рыбалов А. О генерической сложности проблемы общезначимости булевых формул // Прикладная дискретная математика. 2016. №2(32). С. 119-126.
О генерической сложности проблемы разбиения графа на треугольники | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/10
О генерической сложности проблемы разбиения графа на треугольники | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/10