Geodesic
Generic complexity of first-order theories
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 8 (2011), pp. 168-178.

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

Theory of generic complexity studies algorithmical problems for “almost all” inputs. A problem can be hard or undecidable in the worst case but feasible in the generic case. In this review we describe some recent results about generic complexity of the following first order theories: any undecidable first order theory (Mysnikov, Rybalov), ordered field of real numbers (Rybalov, Fedosov), Presburger arithmetic (Rybalov).
Keywords: generic complexity, first order theory. 
@article{SEMR_2011_8_a14,
     author = {A. N. Rybalov},
     title = {Generic complexity of first-order theories},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {168--178},
     publisher = {mathdoc},
     volume = {8},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2011_8_a14/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - Generic complexity of first-order theories
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2011
SP  - 168
EP  - 178
VL  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2011_8_a14/
LA  - ru
ID  - SEMR_2011_8_a14
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T Generic complexity of first-order theories
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2011
%P 168-178
%V 8
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2011_8_a14/
%G ru
%F SEMR_2011_8_a14
A. N. Rybalov. Generic complexity of first-order theories. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 8 (2011), pp. 168-178. http://geodesic.mathdoc.fr/item/SEMR_2011_8_a14/

[1] A. Bogdanov, L. Trevisan, Average-Case Complexity, Electronic Colloquium on Computational Complexity, Report No. 73, 2006 | MR

[2] M.J. Fischer, M.O. Rabin, “Super-Exponential Complexity of Presburger Arithmetic”, Proceedings of the SIAM-AMS Symposium in Applied Mathematics, 7 (1974), 27–41 | MR

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

[4] Impagliazzo R., Wigderson A., “P = BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma”, Proceedings of the 29th STOC, 1997, ACM, New York, 1999, 220–229 | MR | Zbl

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

[6] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain, “Average-case complexity and decision problems in group theory”, Advances in Mathematics, 190 (2005), 343–359 | DOI | MR | Zbl

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

[8] A. Rybalov, “Generic Complexity of Presburger Arithmetic”, Theory of Computing Systems, 46:1 (2010), 2–8 | DOI | MR | Zbl

[9] D. Knut, Iskusstvo programmirovaniya, Izd. Vilyams, 2010

[10] A. Rybalov, V. Fedosov, “Genericheskaya slozhnost algebry Tarskogo”, Vestnik Omskogo universiteta, 2011, no. 2, 21–25

[11] A. Spivak, “Chisla Katalana”, Kvant, 2004, no. 3, 2–10