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/

[1] Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl

[2] Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Average-case complexity for the word and membership problems in group theory”, Adv. Math., 190 (2005), 343–359 | DOI | MR | Zbl

[3] Hamkins J. D., Miasnikov A. G., “The halting problem is decidable on a set of asymptotic probability one”, Notre Dame J. Formal Logic, 47:4 (2006), 515–524 | DOI | MR | Zbl

[4] Gilman R., Miasnikov A. G., Myasnikov A. D., Ushakov A., “Report on generic case complexity”, Herald of Omsk University, 2007, Special Issue, 103–110

[5] Cook S. A., “The complexity of theorem proving procedures”, Proc. 3d Annual ACM Symposium on Theory of Computing, N.Y., USA, 1971, 151–158 | Zbl

[6] Impagliazzo R., Wigderson A., “P=BPP unless E has subexponential circuits: Derandomizing the XOR Lemma”, Proc. 29th STOC., ACM, El Paso, 1997, 220–229 | MR

[7] Myasnikov A., Rybalov A., “Generic complexity of undecidable problems”, J. Symbolic Logic, 73:2 (2008), 656–673 | DOI | MR | Zbl

[8] Rybalov A., “Generic complexity of presburger arithmetic”, Theory Comput. Systems, 46:1 (2010), 2–8 | DOI | MR | Zbl

[9] Knuth D. E., The Art of Computer Programming, Addison-Wesley, Reading, Massachusetts, 1997 | MR | Zbl