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

О генерической сложности проблемы распознавания квадратичных вычетов | Прикладная дискретная математика. 2015. № 2 (28).

Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность классической проблемы распознавания квадратичных вычетов в группах вычетов. Доказывается, что её естественная подпроблема генерически трудноразрешима (то есть трудна для почти всех входов) при условии, что проблема распознавания квадратичных вычетов трудноразрешима в классическом смысле.
  • Title О генерической сложности проблемы распознавания квадратичных вычетов
  • Headline О генерической сложности проблемы распознавания квадратичных вычетов
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2 (28)
  • Date:
  • DOI
Ключевые слова
генерическая сложность, квадратичный вычет, вероятностный алгоритм, generic complexity, quadratic residue, probabilistic algorithm
Авторы
Ссылки
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.
Kapovich I., Miasnikov A., Schupp P., and Shpilrain V. Average-case complexity for the word and membership problems in group theory // Adv. Math. 2005. V. 190. P. 343-359.
Hamkins J. D. and Miasnikov A. G. The halting problem is decidable on a set of asymptotic probability one // Notre Dame J. Formal Logic. 2006. V. 47. No. 4. P. 515-524.
Gilman R., Miasnikov A. G., Myasnikov A. D., and Ushakov A. Report on generic case complexity // Herald of Omsk University. 2007. Special Issue. P. 103-110.
Blum M. and Micali S. How to generate cryptographically strong sequences of pseudorandom bits // SIAM J. Comput. 1984. V. 13. No. 4. P. 850-864.
Мао В. Современная криптография: теория и практика. М.: Вильямс, 2005. 768с.
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.
Myasnikov A. and Rybalov A. Generic complexity of undecidable problems // J. Symbolic Logic. 2008. V. 73. No. 2. P. 656-673.
Rybalov A. Generic complexity of Presburger Arithmetic // Theory Comput. Systems. 2010. V. 46. No. 1. P. 2-8.
О генерической сложности проблемы распознавания квадратичных вычетов | Прикладная дискретная математика. 2015. № 2 (28).
О генерической сложности проблемы распознавания квадратичных вычетов | Прикладная дискретная математика. 2015. № 2 (28).