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

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

Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В данной работе изучается генерическая сложность проблемы общезначимости (тождественной истинности) булевых формул. Доказывается, что эта проблема неразрешима за полиномиальное время на любом полиномиальном строго генерическом множестве формул при условии её трудноразрешимости в худшем случае.
  • Title О генерической сложности проблемы общезначимости булевых формул
  • Headline О генерической сложности проблемы общезначимости булевых формул
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(32)
  • Date:
  • DOI
Ключевые слова
генерическая сложность, проблема общезначимости булевых формул, generic complexity, validity problem for Boolean formulas
Авторы
Ссылки
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.
Cook S. A. The complexity of theorem proving procedures // Proc. 3d Annual ACM Symposium on Theory of Computing. N. Y., USA, 1971. P. 151-158.
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.
Кнут Д. Искусство программирования. М.: Вильямс, 2010. 720 с.
О генерической сложности проблемы общезначимости булевых формул | Прикладная дискретная математика. 2016. № 2(32).
О генерической сложности проблемы общезначимости булевых формул | Прикладная дискретная математика. 2016. № 2(32).