Geodesic
On generic complexity of the validity problem for Boolean formulas
Prikladnaâ diskretnaâ matematika, no. 2 (2016), pp. 119-126

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{PDM_2016_2_a8,
     author = {A. N. Rybalov},
     title = {On generic complexity of the validity problem for {Boolean} formulas},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {119--126},
     publisher = {mathdoc},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2016_2_a8/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On generic complexity of the validity problem for Boolean formulas
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2016
SP  - 119
EP  - 126
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2016_2_a8/
LA  - ru
ID  - PDM_2016_2_a8
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On generic complexity of the validity problem for Boolean formulas
%J Prikladnaâ diskretnaâ matematika
%D 2016
%P 119-126
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2016_2_a8/
%G ru
%F PDM_2016_2_a8
A. N. Rybalov. On generic complexity of the validity problem for Boolean formulas. Prikladnaâ diskretnaâ matematika, no. 2 (2016), pp. 119-126. http://geodesic.mathdoc.fr/item/PDM_2016_2_a8/