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/