Geodesic
Decidability of classes of algebraic systems in polynomial time
Sbornik. Mathematics, Tome 193 (2002) no. 2, pp. 157-186 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

For some classes of algebraic systems several kinds of polynomial-time decidability are considered, which use an oracle performing signature operations and computing predicates. Relationships between various kinds of decidability are studied. Several results on decidability and undecidability in polynomial time are proved for some finitely based varieties of universal algebras. 
@article{SM_2002_193_2_a0,
     author = {M. I. Anokhin},
     title = {Decidability of classes of algebraic systems in polynomial time},
     journal = {Sbornik. Mathematics},
     pages = {157--186},
     year = {2002},
     volume = {193},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2002_193_2_a0/}
}
TY  - JOUR
AU  - M. I. Anokhin
TI  - Decidability of classes of algebraic systems in polynomial time
JO  - Sbornik. Mathematics
PY  - 2002
SP  - 157
EP  - 186
VL  - 193
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SM_2002_193_2_a0/
LA  - en
ID  - SM_2002_193_2_a0
ER  - 
%0 Journal Article
%A M. I. Anokhin
%T Decidability of classes of algebraic systems in polynomial time
%J Sbornik. Mathematics
%D 2002
%P 157-186
%V 193
%N 2
%U http://geodesic.mathdoc.fr/item/SM_2002_193_2_a0/
%G en
%F SM_2002_193_2_a0
M. I. Anokhin. Decidability of classes of algebraic systems in polynomial time. Sbornik. Mathematics, Tome 193 (2002) no. 2, pp. 157-186. http://geodesic.mathdoc.fr/item/SM_2002_193_2_a0/

[1] Babai L., Szemerédi E., “On the complexity of matrix group problems, I”, Proc. 25th Annual IEEE Symp. on Foundations of Computer Science (Singer Island, Florida, October 24–26, 1984), 1984, 229–240

[2] Shoup V., “Lower bounds for discrete logarithms and related problems”, Advances in Cryptology – EUROCRYPT'97, Proc. Internat. Conf. on the Theory and Application of Cryptographic Techniques (Konstanz, Germany, May 11–15, 1997), Lecture Notes in Comput. Sci., 1233, Springer-Verlag, Berlin, 1997, 256–266 | MR

[3] Nechaev V. I., “K voprosu o slozhnosti determinirovannogo algoritma dlya diskretnogo logarifma”, Matem. zametki, 55:2 (1994), 91–101 | MR | Zbl

[4] Boneh D., Lipton R. J., “Algorithms for black-box fields and their application to cryptography”, Advances in Cryptology – CRYPTO'96, Proc. 16th Annual Internat. Cryptology Conf. (Santa Barbara, California, August 18–22, 1996), Lecture Notes in Comput. Sci., 1109, Springer-Verlag, Berlin, 1996, 283–297

[5] Babai L., Cooperman G., Finkelstein L., Luks E., Seress Á., “Fast Monte Carlo algorithms for permutation groups”, Proc. 23rd Annual ACM Symp. on Theory of Computing (New Orleans, Louisiana, May 6–8, 1991), 1991, 90–100; J. Comput. System Sci., 50:2 (1995), 296–308 | DOI | MR | Zbl

[6] Babai L., “Local expansion of vertex-transitive graphs and random generation in finite groups”, Proc. 23rd Annual ACM Symp. on Theory of Computing (New Orleans, Louisiana, May 6–8, 1991), 1991, 164–174

[7] Impagliazzo R., Naor M., “Efficient cryptographic schemes provably as secure as subset sum”, J. Cryptology, 9:4 (1996), 199–216 | DOI | MR | Zbl

[8] Bakhturin Yu. A., Olshanskii A. Yu., “Tozhdestva”, Itogi nauki i tekhniki. Sovrem. probl. matem. Fundam. napr., 18, VINITI, M., 1988, 117–240 | MR

[9] Goldreich O., Introduction to complexity theory. Lecture notes for a two-semester course (1999), $html/cc.html} http://www.wisdom.weizmann.ac.il/\allowbreakõded/public<nobr>$\underline{\phantom n | Zbl

[10] Neiman Kh., Mnogoobraziya grupp, Mir, M., 1969 | MR

[11] Skornyakov L. A., Elementy obschei algebry, Nauka, M., 1983 | MR | Zbl

[12] Shemetkov L. A., Skiba A. S., Formatsii algebraicheskikh sistem, Nauka, M., 1989 | MR

[13] Kitaev A., Shen A., Vyalyi M., Klassicheskie i kvantovye vychisleniya, MTsNMO – CheRo, M., 1999

[14] Erdős P., Rényi A., “Probabilistic methods in group theory”, J. Anal. Math., 14 (1965), 127–138 | DOI | MR | Zbl

[15] Vaughan-Lee M. R., “Abelian by nilpotent varieties”, Quart. J. Math. Oxford Ser. (2), 21:82 (1970), 193–202 | DOI | MR | Zbl

[16] Vaughan-Lee M. R., “Abelian-by-nilpotent varieties of Lie algebras”, J. London Math. Soc. (2), 11:3 (1975), 263–266 | DOI | MR | Zbl

[17] Ekhad S. B., Zeilberger D., “There are more than $2^{n/17}$ $n$-letter ternary square-free words”, Article 98.1.9, J. Integer Sequences (electronic), 1 (1998) ; $njas/sequences/JIS/zeil.html} http://www.research.att.com/<nobr>${\sim | MR

[18] Kolpakov R. M., “O chisle trekhbukvennykh beskvadratnykh i dvukhbukvennykh beskubnykh slov”, Tezisy dokladov XII Mezhdunarodnoi konferentsii “Problemy teoreticheskoi kibernetiki” (Nizhnii Novgorod, 17–22 maya 1999 g.), Izd-vo mekhaniko-matematicheskogo fakulteta MGU, M., 1999, 106