Persons
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
 
Rybalov, Alexander Nikolaevich

Total publications: 57 (57)
in MathSciNet: 14 (14)
in zbMATH: 14 (14)
in Web of Science: 35 (35)
in Scopus: 22 (22)
Cited articles: 33
Citations in Math-Net.Ru: 34
Citations in Web of Science: 48
Citations in Scopus: 21
Presentations: 1

Number of views:
This page:1267
Abstract pages:3024
Full texts:866
References:393
Rybalov, Alexander Nikolaevich
Senior Researcher
Candidate of physico-mathematical sciences (2005)
Speciality: 01.01.06 (Mathematical logic, algebra, and number theory)
E-mail:
Keywords: Algorithmic problems, generic complexity, complexity of computations
UDC: 510.52, 510.53
MSC: 03D15 68Q15 68Q17

Subject:

Logica.

   
Main publications:
  1. A. N. Rybalov, “Generic amplification of recursively enumerable sets”, Algebra and Logic, 57:4 (2018), 289–294  mathnet  crossref  crossref  mathscinet  zmath  isi  scopus
  2. A. N. Rybalov, “Generic Gödel's incompleteness theorem”, Algebra and Logic, 56:3 (2017), 232–235  mathnet  crossref  crossref  isi  elib  scopus
  3. A. N. Rybalov, “A generic relation on recursively enumerable sets”, Algebra and Logic, 55:5 (2016), 387–393  mathnet  crossref  crossref  isi  elib  scopus
  4. Rybalov A., “Generic complexity of the Diophantine problem”, Groups Complexity Cryptology, 5:1 (2013) , 25Ц30 pp.  crossref  mathscinet  zmath  scopus
  5. A. Rybalov, “Generic Complexity of Presburger Arithmetic”, Theory of Computing Systems, 46:1 (2010), 2-8  crossref  mathscinet  zmath  isi
  6. A. Rybalov, A. Myasnikov, “Generic complexity of undecidable problems”, Journal of Symbolic Logic, 73:2 (2008), 656-673  crossref  mathscinet  zmath  isi  elib  scopus
  7. A. Rybalov, “On the strongly generic undecidability of the Halting Problem”, Theoretical Computer Science, 377 (2007), 268-270  crossref  mathscinet  zmath  isi  elib  scopus
  8. A. Rybalov, “On the PЦNP problem over real matrix rings”, Theoretical Computer Science, 314:1-2 (2004), 281Ц285  crossref  mathscinet  zmath  isi  elib  scopus

http://www.mathnet.ru/eng/person29654
List of publications on Google Scholar
List of publications on ZentralBlatt
https://mathscinet.ams.org/mathscinet/MRAuthorID/607051
http://orcid.org/0000-0002-2269-589X
http://www.researcherid.com/rid/G-3081-2013
https://www.scopus.com/authid/detail.url?authorId=57190706642

Full list of scientific publications:
| scientific publications | by years | by types | by times cited in WoS | by times cited in Scopus | common list |



   2021
1. A. Rybalov, “Generic complexity of algorithmic problems over Brandt semigroups”, Journal of Physics: Conference series, 1791 (2021), 1–10 (012085)  crossref  scopus
2. A. Rybalov, “O genericheskoi slozhnosti problemy izomorfizma konechnykh polugrupp”, Prikladnaya diskretnaya matematika, 51 (2021), 120–128  mathnet  crossref  isi  elib
3. A. N. Rybalov, “On generic complexity of the isomorphism problem for finite semigroups”, Prikl. Diskr. Mat. Suppl., 2021, no. 14, 178–180  mathnet  crossref
4. A. Rybalov, “On generic complexity of the problem of searching of isomorphism for finite semigroups”, Journal of Physics: Conference series, 1901 (2021), 012045 , 6 pp.  crossref  scopus
5. A. Rybalov, “On generic complexity of theories of finite algebraic structures”, Journal of Physics: Conference series, 1901 (2021), 012046 , 7 pp.  crossref  scopus
6. A. Rybalov, A. Shevlyakov, “Generic complexity of solving of equations in finite groups, semigroups and fields”, Journal of Physics: Conference series, 1901 (2021), 012047 , 8 pp.  crossref  scopus
7. A. Rybalov, A. Shevlyakov, “Equationally extreme trees”, Journal of Physics: Conference series, 1901 (2021), 012048 , 7 pp.  crossref  scopus
8. A. N. Rybalov, “The general complexity of the problem to recognize Hamiltonian paths”, Prikl. Diskr. Mat., 2021, no. 53, 120–126  mathnet  crossref

   2020
9. A. N. Rybalov, “On generic NP-completeness of the problem of Boolean circuits satisfiability”, Prikl. Diskr. Mat., 2020, no. 47, 101–107  mathnet  crossref  isi
10. A. Rybalov, “A generic algorithm for the word problem in semigroups and groups”, Journal of Physics: Conference Series, 1546 (2020), 1–10 , 012100  crossref  isi  scopus
11. A. Rybalov, “A generic algorithm for the identity problem in finite groups and monoids”, Journal of Physics: Conference Series, 1546 (2020), 1–6 , 012101  crossref  isi  scopus (cited: 1)
12. A. Rybalov, “O genericheskoi slozhnosti problemy predstavimosti naturalnykh chisel summoi dvukh kvadratov”, Prikladnaya diskretnaya matematika, 2020, no. 48, 93–99  mathnet (cited: 1)  crossref  isi
13. A. Rybalov, “Neplotnost genericheskoi m-svodimosti dlya rekursivno perechislimykh mnozhestv”, Vestnik Omskogo universiteta, 25:2 (2020), 9–12  crossref
14. A. Rybalov, “O genericheskoi slozhnosti ekzistentsialnykh teorii”, Prikladnaya diskretnaya matematika, 2020, no. 49, 120–126  mathnet (cited: 1)  crossref  isi
15. A. Rybalov, “On the generic existential theory of finite graphs”, Siberian Elecronic Mathematical Reports, 17 (2020), 1710–1714  mathnet  crossref  isi  scopus (cited: 3)
16. A. Rybalov, “O genericheskoi slozhnosti problemy o summe podmnozhestv dlya polugrupp tselochislennykh matrits”, Prikladnaya diskretnaya matematika, 2020, no. 50, 118–126  mathnet  crossref  isi
17. A. Rybalov, “O genericheskoi slozhnosti problemy o summe podmnozhestv v monoidakh i gruppakh tselochislennykh matrits vtorogo poryadka”, Vestnik Omskogo universiteta, 25:4 (2020), 10–15
18. A. N. Rybalov, “On generic complexity of the problem to represent natural numbers by sum of two squares”, Prikl. Diskr. Mat. Suppl., 2020, no. 13, 111–113  mathnet  crossref

   2019
19. A. Rybalov, “O genericheskoi nerazreshimosti desyatoi problemy Gilberta dlya polinomialnykh derevev”, Prikladnaya diskretnaya matematika, 2019, no. 44, 107-112  mathnet (cited: 1)  crossref  isi  elib  scopus (cited: 4)
20. A. N. Rybalov, “On the generic complexity of the decoding problem for linear codes”, Prikl. Diskr. Mat. Suppl., 2019, no. 12, 198–202  mathnet  crossref  elib
21. A. Rybalov, “Genericheskaya nerazreshimost universalnykh teorii”, Sibirskie elektronnye matematicheskie izvestiya, 16 (2019), 1289-1294  mathnet  crossref  mathscinet  zmath  isi
22. A. Rybalov, “O slozhnosti ekzistentsialnoi i universalnoi teorii konechnykh polei”, Prikladnaya diskretnaya matematika, 2019, no. 45, 85-89  mathnet (cited: 1)  crossref  isi  elib
23. A. Rybalov, “O genericheskoi slozhnosti problemy klasterizatsii grafov”, Prikladnaya diskretnaya matematika, 2019, no. 46, 72–77  mathnet  crossref  isi

   2018
24. A. Y. Nikitin, A. N. Rybalov, “On complexity of the satisfiability problem of systems over finite posets”, Prikl. Diskr. Mat., 2018, no. 39, 94–98  mathnet  crossref  isi  elib
25. A. N. Rybalov, “Relativized generic classes $\mathrm P$ and $\mathrm{NP}$”, Prikl. Diskr. Mat., 2018, no. 40, 100–104  mathnet  crossref  isi  elib
26. A. N. Rybalov, “On the generic complexity of discrete logarithm problem in groups of elliptic curves over finite fields”, Prikl. Diskr. Mat. Suppl., 2018, no. 11, 133–136  mathnet  crossref  elib
27. A. N. Rybalov, “Generic amplification of recursively enumerable sets”, Algebra and Logic, 57:4 (2018), 289–294  mathnet  crossref  crossref  mathscinet  zmath  isi  scopus (cited: 2)
28. A. Rybalov, “A generic m-reducibility”, Lecture Notes in Computer Science, 10936 (2018), 359–364  crossref  mathscinet  zmath  isi  scopus

   2017
29. A. N. Rybalov, “On generic NP-completeness of the Boolean satisfiability problem”, Prikl. Diskr. Mat., 2017, no. 36, 106–112  mathnet  crossref  isi  elib
30. A. N. Rybalov, “Generic Kleene fixed point theorem”, Sib. Èlektron. Mat. Izv., 14 (2017), 732–736  mathnet  crossref  isi
31. A. N. Rybalov, “On generic complexity of decidability problem for Diophantine systems in the Skolem's form”, Prikl. Diskr. Mat., 2017, no. 37, 100–106  mathnet  crossref  isi  elib
32. A. N. Rybalov, “Generic Gödel's incompleteness theorem”, Algebra and Logic, 56:3 (2017), 232–235  mathnet  crossref  crossref  isi  elib  scopus
33. A. N. Rybalov, “On generic complexity of the problem of finding roots in groups of residues”, Prikl. Diskr. Mat., 2017, no. 38, 95–100  mathnet  crossref  isi  elib
34. A. Rybalov, “On the generic undecidability of the Halting Problem for normalized Turing machines”, Theory of Computing Systems, 60:4 (2017), 671-676  crossref  mathscinet  zmath  isi  scopus (cited: 2)
35. A. Rybalov, “Generic hardness of the Boolean satisfiability problem”, Groups Complexity Cryptology, 9:2 (2017), 151-154  crossref  mathscinet  zmath  isi  elib  scopus (cited: 1)

   2016
36. A. N. Rybalov, “On generic complexity of the validity problem for Boolean formulas”, Prikl. Diskr. Mat., 2016, no. 2, 119–126  mathnet  crossref  isi  elib
37. A. N. Rybalov, “Generic undecidability of existential theory of integer numbers ring”, Sib. Èlektron. Mat. Izv., 13 (2016), 882–887  mathnet  crossref  isi  elib
38. A. N. Rybalov, “On generic complexity of the discrete logarithm problem”, Prikl. Diskr. Mat., 2016, no. 3, 93–97  mathnet  crossref  isi  elib
39. A. N. Rybalov, “A generic relation on recursively enumerable sets”, Algebra and Logic, 55:5 (2016), 387–393  mathnet  crossref  crossref  isi (cited: 1)  elib  scopus
40. G. Noskov, A. Rybalov, “Generic case complexity of the Graph Isomorphism Problem”, Groups Complexity Cryptology, 8:1 (2016), 9-20  crossref  mathscinet  zmath  isi  scopus

   2015
41. A. N. Rybalov, “Generic incompleteness of formal arithmetic”, Sib. Èlektron. Mat. Izv., 12 (2015), 185–189  mathnet  crossref  elib
42. A. N. Rybalov, “On generic complexity of the quadratic residuosity problem”, Prikl. Diskr. Mat., 2015, no. 2, 54–58  mathnet  crossref  isi  elib
43. A. Rybalov, “On the generic complexity of the searching graph isomorphism problem”, Groups Complexity Cryptology, 7:2 (2015), 191-194  crossref  mathscinet  scopus (cited: 3)
44. A. N. Rybalov, “On generic complexity of the quadratic residuosity problem”, Prikl. Diskr. Mat. Suppl., 2015, no. 8, 71–73  mathnet  crossref

   2013
45. Rybalov A., “Generic complexity of the Diophantine problem”, Groups Complexity Cryptology, 5:1 (2013) , 25Ц30 pp.  crossref  mathscinet  zmath  scopus (cited: 5)

   2011
46. A. Rybalov, “O genericheskoi nerazreshimosti Desyatoi problemy Gilberta”, Vestnik Omskogo universiteta, 2011, no. 4, 19-22  elib (cited: 1)
47. A.N. Rybalov, “Generic complexity of first-order theories”, Siberian Elektronic Mathematical report, 8 (2011), 168–178  mathnet  elib

   2010
48. A. Rybalov, “Generic Complexity of Presburger Arithmetic”, Theory of Computing Systems, 46:1 (2010), 2-8  crossref  mathscinet  zmath  isi (cited: 8)
49. Rybalov A., “Polinomialnye klassy slozhnosti nad veschestvennymi algebrami s nilpotentnymi elementami”, Vestnik Omskogo universiteta, 2010, no. 4, 37-41  elib (cited: 1)

   2009
50. Rybalov A.N., “GENERIC COMPLEXITY OF PRESBURGER ARITHMETIC”, Theory of Computing Systems, 46:1 (2009), http://link.springer.com/article/10.1007 , 2-8 pp.  mathscinet  elib (cited: 11)

   2008
51. A. Rybalov, A. Myasnikov, “Generic complexity of undecidable problems”, Journal of Symbolic Logic, 73:2 (2008), 656-673  crossref  mathscinet  zmath  isi (cited: 25)  elib (cited: 21)  scopus

   2007
52. A. Rybalov, “On the strongly generic undecidability of the Halting Problem”, Theoretical Computer Science, 377 (2007), 268-270  crossref  mathscinet  zmath  isi (cited: 11)  elib (cited: 9)  scopus
53. Rybalov Alexander N., “Generic complexity of presburger arithmetic Source: Computer Science - Theory and Applications Book”, Sponsor(s): European Assoc Theroet Comp Sci, Computer Science - Theory and Applications Book, Conference: 2nd International Computer Science Symposium in Russia (CSR 2007) (Ekaterinburg, RUSSIA SEP 03-0), Series: LECTURE NOTES IN COMPUTER SCIENCE, 4649, eds. Editor(s): Diekert V; Volkov MV; Voronkov A, Ekaterinburg, RUSSIA, 2007, 356-361  crossref  zmath  isi  elib (cited: 1)

   2005
54. Rybalov A.N., SLOZhNOST VYChISLENII V ALGEBRAIChESKIKh SISTEMAKh, avtoreferat dissertatsii na soiskanie uchenoi stepeni kandidata fiziko-matematicheskikh nauk, Omskii gosudarstvennyi universite, Omsk, 2005 , 15 pp.  elib

   2004
55. A. Rybalov, “On the PЦNP problem over real matrix rings”, Theoretical Computer Science, 314:1-2 (2004), 281Ц285  crossref  mathscinet  zmath  isi (cited: 2)  elib (cited: 2)  scopus
56. Rybalov A. N., “Relativizations of the P=NP problem over the complex number field,”, Siberian Elektronic Mathematical report, 1 (2004), 91-98  mathnet  mathscinet  zmath
57. A. N. Rybalov, “Computational complexity in algebraic systems”, Siberian Math. J., 45:6 (2004), 1113–1123  mathnet  crossref  mathscinet  zmath  isi  elib  scopus

Presentations in Math-Net.Ru
1. Ќовые проблемы алгебры и логики. ёбилейное 900-е заседание семинара
V. N. Remeslennikov, A. N. Rybalov, A. N. Shevlyakov, D. V. Solomatin, L. M. Martynov, G. A. Noskov, A. V. Treyer, A. N. Zubkov, V. P. Il'ev, V. M. Gichev
Omsk Algebraic Seminar
November 12, 2015 16:00

Organisations
 
Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021