|
This article is cited in 6 scientific papers (total in 6 papers)
Mathematical Foundations of Informatics and Programming
On generic complexity of the validity problem for Boolean formulas
A. N. Rybalov Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia
Abstract:
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.
Keywords:
generic complexity, validity problem for Boolean formulas.
Citation:
A. N. Rybalov, “On generic complexity of the validity problem for Boolean formulas”, Prikl. Diskr. Mat., 2016, no. 2(32), 119–126
Linking options:
https://www.mathnet.ru/eng/pdm547 https://www.mathnet.ru/eng/pdm/y2016/i2/p119
|
Statistics & downloads: |
Abstract page: | 212 | Full-text PDF : | 61 | References: | 36 |
|