HomeIssuesOn generic complexity of the validity problem for Boolean formulas

On generic complexity of the validity problem for Boolean formulas | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 2(32).

Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. In this paper, we consider generic complexity of the validity problem for Boolean formulas and prove that this problem is generically hard if it is hard in the worst case.
Download file
Counter downloads: 301
  • Title On generic complexity of the validity problem for Boolean formulas
  • Headline On generic complexity of the validity problem for Boolean formulas
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(32)
  • Date:
  • DOI
Keywords
генерическая сложность, проблема общезначимости булевых формул, generic complexity, validity problem for Boolean formulas
Authors
References
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 с.
On generic complexity of the validity problem for Boolean formulas | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 2(32).
On generic complexity of the validity problem for Boolean formulas | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 2(32).
Download full-text version
Counter downloads: 1010