Geodesic
On the complexity of the inversion of discrete functions of a certain class
Diskretnyj analiz i issledovanie operacij, Tome 11 (2004) no. 4, pp. 44-55.

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

@article{DA_2004_11_4_a3,
     author = {A. A. Semenov},
     title = {On the complexity of the inversion of discrete functions of a certain class},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {44--55},
     publisher = {mathdoc},
     volume = {11},
     number = {4},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2004_11_4_a3/}
}
TY  - JOUR
AU  - A. A. Semenov
TI  - On the complexity of the inversion of discrete functions of a certain class
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2004
SP  - 44
EP  - 55
VL  - 11
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2004_11_4_a3/
LA  - ru
ID  - DA_2004_11_4_a3
ER  - 
%0 Journal Article
%A A. A. Semenov
%T On the complexity of the inversion of discrete functions of a certain class
%J Diskretnyj analiz i issledovanie operacij
%D 2004
%P 44-55
%V 11
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2004_11_4_a3/
%G ru
%F DA_2004_11_4_a3
A. A. Semenov. On the complexity of the inversion of discrete functions of a certain class. Diskretnyj analiz i issledovanie operacij, Tome 11 (2004) no. 4, pp. 44-55. http://geodesic.mathdoc.fr/item/DA_2004_11_4_a3/

[1] Bespalov D. V., Semenov A. A., “O logicheskikh vyrazheniyakh dlya zadachi 2-FAKTORIZATsIYa”, Vychislitelnye tekhnologii, 7: chast 2 (2002), 18–25

[2] Vinogradov I. M., Osnovy teorii chisel, Nauka, M., 1981 | MR

[3] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[4] Levin L. A., “Odnostoronnie funktsii”, Problemy peredachi informatsii, 39:1 (2003), 103–117 | MR | Zbl

[5] Semenov A. A., “Zamechanie o vychislitelnoi slozhnosti izvestnykh predpolozhitelno odnostoronnikh funktsii”, Trudy XII Baikalskoi mezhdunarodnoi konferentsii “Metody optimizatsii i ikh prilozheniya”, T. 5. Diskretnaya matematika (Irkutsk, 24 iyunya–1 iyulya 2001 g.), Izd-vo IrGU, Irkutsk, 2001, 142–146

[6] Agrawal M., Kayal N., Saxena N., Primes is in P, Preprint, Department of Computer Science and Engineering Indian Institute of Technology, Kanpur, India, 2002 | MR

[7] Cook S. A., “The complexity of theorem-proving procedures”, Proc. of the third annual ACM symposium on theory of computing (Ohio, May 3–5, 1971), IEEE, New York, 1971, 151–158; Kuk S. A., “Slozhnost protsedur vyvoda teorem”, Kiberneticheskii sbornik. Novaya seriya, no. 12, Mir, M., 1975, 5–15

[8] Goldreich O., Introduction to complexity theory, Lecture Notes, Weizmann Institute of Science, Israel, 1999

[9] Rivest R., Shamir A., Adleman L., “A method for obtaining digital signatures and public-key cryptosystems”, Commun. ACM, 21:2 (1978), 120–126 | DOI | MR | Zbl

[10] Simon J., On some central problems in computational complexity, Doctoral Thesis, Cornel University, Ithaca, NY, 1975