В рамках генерического подхода изучается поведение алгоритмов на типичных (почти всех) входах, а осталвные входы игнорируются. А. Мясниковым и автором ранее был предложен метод генерической амплификации для построения генерически неразрешимых алгоритмических проблем. Основной идеей этого метода является объединение эквивалентных входов в достаточно болвшие множества. Эквивалентности входов означает, что рассматриваемая проблема на них решается одинаково. Предлагается обобщение этого метода, строится пример разрешимой в классическом смысле проблемы, не являющейся генерически разрешимой за полиномиалвное время. Для этого исполвзуются другие методы, так как, скорее всего, метод генерической амплификации здесв не работает.
Скачать электронную версию публикации
Загружен, раз: 72
- Title Генерически неразрешимые и трудноразрешимые проблемы
- Headline Генерически неразрешимые и трудноразрешимые проблемы
- Publesher
Tomsk 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
Скачать полнотекстовую версию
Загружен, раз: 96
- ВКонтакте
- РћРТвЂВВВВВВВВнокласснРСвЂВВВВВВВВРєРСвЂВВВВВВВВ
- Telegram