Генерически неразрешимые и трудноразрешимые проблемы | Прикладная дискретная математика. 2024. № 63. DOI: 10.17223/20710410/63/7

В рамках генерического подхода изучается поведение алгоритмов на типичных (почти всех) входах, а осталвные входы игнорируются. А. Мясниковым и автором ранее был предложен метод генерической амплификации для построения генерически неразрешимых алгоритмических проблем. Основной идеей этого метода является объединение эквивалентных входов в достаточно болвшие множества. Эквивалентности входов означает, что рассматриваемая проблема на них решается одинаково. Предлагается обобщение этого метода, строится пример разрешимой в классическом смысле проблемы, не являющейся генерически разрешимой за полиномиалвное время. Для этого исполвзуются другие методы, так как, скорее всего, метод генерической амплификации здесв не работает.
  • Title Генерически неразрешимые и трудноразрешимые проблемы
  • Headline Генерически неразрешимые и трудноразрешимые проблемы
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 63
  • Date:
  • DOI 10.17223/20710410/63/7
Ключевые слова
генерическая сложность, амплификация, алгоритмическая, проблема
Авторы
Ссылки
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.
Myasnikov A. and Rybalov A. Generic complexity of undecidable problems //j. Symbolic Logic. 2008. V.73. No.2. P.656-673.
Rybalov A. On the generic undecidabilitv of the Halting Problem for normalized Turing machines // Theory of Computing Systems. 2017. V. 60. No. 4. P.671-676.
Рыбалов A. H. О генерической сложности элементарных теорий // Вестник Омского университета. 2015. №4. С. 14-17.
Rybalov A. Generic complexity of the Diophantine problem // Groups Complexity Cryptology. 2013. V.5. No. 1. P.25-30.
Rybalov A. Generic complexity of Presburger arithmetic // Theory of Computing Systems. 2010. V.46. No. 1. P.2-8.
Hirschfeldt D. Some questions in computable mathematics // LNCS. 2017. V. 10010. P. 22-55.
Jockusch C. and Schupp P. Generic computability, Turing degrees, and asymptotic density //j. London Math. Soc. 2012. V.85. No.2. P.472-490.
Gilman A., Myasnikov A., and Roman’kov V.A. Random equations in free groups // Groups Complexity Cryptology. 2011. V.3. No. 2. P.257-284.
Gilman A., Myasnikov A., and Roman’kov V.A. Random equations in nilpotent groups //j. Algebra. 2012. V.352. No. 1. P. 192-214.
 Генерически неразрешимые и трудноразрешимые проблемы | Прикладная дискретная математика. 2024. № 63. DOI: 10.17223/20710410/63/7
Генерически неразрешимые и трудноразрешимые проблемы | Прикладная дискретная математика. 2024. № 63. DOI: 10.17223/20710410/63/7