Persons: Rybalov, Alexander Nikolaevich

Persons

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

Rybalov, Alexander Nikolaevich

Statistics
in MathSciNet:	15 (15)
in zbMATH:	14 (14)
in Web of Science:	51 (51)
in Scopus:	40 (40)

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:

Algorithmic problems in algebra, logic and number theory. Generic complexity, complexity of computations.

Main publications:

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

https://www.mathnet.ru/eng/person29654

List of publications on Google Scholar

https://mathscinet.ams.org/mathscinet/MRAuthorID/607051

https://orcid.org/0000-0002-2269-589X

https://www.webofscience.com/wos/author/record/G-3081-2013

https://www.scopus.com/authid/detail.url?authorId=57190706642

List of scientific publications:

scientific publications

		Citations (Crossref Cited-By Service + Math-Net.Ru)

1.	Lopatin A.A., Rybalov A.N., “O genericheskoi slozhnosti resheniya uravnenii nad bitsiklicheskim monoidom”, Prikladnaya diskretnaya matematika, 2025, no. 67, 110–117
2.	Lopatin A., Rybalov A., “On polynomial equations over split octonions”, Communications in Mathematics, 33:3 (2025), 8 , 12 pp.
3.	Rybalov A., “O probleme P=NP v nekotorykh koltsakh”, Sibirskie elektronnye matematicheskie izvestiya, 22:1 (2025), 683–691
4.	D. P. Ruzanova, A. N. Rybalov, “On the generic complexity of graph $3$-coloring problems”, Prikl. Diskr. Mat., 2025, no. 69, 121–128
5.	Rybalov A., “O genericheskoi slozhnosti resheniya uravnenii v konechnykh predikatnykh algebraicheskikh sistemakh”, Prikladnaya diskretnaya matematika, 2025, no. 70, 102–109
6.	Rybalov A., “O slozhnosti problemy ravenstva v polugruppakh s usloviem odnorodnosti opredelyayuschikh sootnoshenii”, Sibirskie elektronnye matematicheskie izvestiya, 21:1 (2024), 55–61
7.	Rybalov A., “O slozhnosti resheniya uravnenii nad grafami”, Sibirskie elektronnye matematicheskie izvestiya, 21:1 (2024), 62–69 $https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT={https://www.webofscience.com/wos/woscc/full-record/WOS:001164416300005?SID=EUW1ED0D6C5XZqMvXoDfSsONEWUa6}$	1 ^[x]
8.	Rybalov A., “Genericheski nerazreshimye i trudnorazreshimye problemy”, Prikladnaya diskretnaya matematika, 2024, no. 63, 109–116	1 ^[x]
9.	Rybalov A., “O genericheskoi slozhnosti resheniya uravnenii nad naturalnymi chislami so slozheniem”, Prikladnaya diskretnaya matematika, 2024, no. 64, 72–78	1 ^[x]
10.	Rybalov A., “O genericheskoi slozhnosti problemy vychisleniya funktsii Eilera”, Prikladnaya diskretnaya matematika, 2024, no. 65, 110–117
11.	Rybalov A., “O genericheskoi slozhnosti problemy diskretnogo logarifma v posledovatelnostyakh Lyuka”, Prikladnaya diskretnaya matematika, 2024, no. 66, 116–122
12.	Rybalov A., “Genericheskie polinomialnye algoritmy dlya problemy o ryukzake v nekotorykh matrichnykh polugruppakh”, Sibirskie elektronnye matematicheskie izvestiya, 20:1 (2023), 100–109
13.	Rybalov A., “O genericheskoi slozhnosti problemy klasterizatsii grafov s ogranicheniyami na razmer klasterov”, Prikladnaya diskretnaya matematika, 2023, no. 60, 114–119
14.	Rybalov A., “O genericheskoi slozhnosti problemy faktorizatsii tselykh chisel”, Prikladnaya diskretnaya matematika, 2023, no. 61, 121–126
15.	Rybalov A., “O genericheskoi slozhnosti problemy izvlecheniya kvadratnogo kornya po prostomu modulyu”, Prikladnaya diskretnaya matematika, 2023, no. 62, 119–123
16.	A. N. Rybalov, “Generic complexity of the membership problem for semigroups of integer matrices”, Prikl. Diskr. Mat., 2022, no. 55, 95–101
17.	A. N. Rybalov, “The generic complexity of the bounded problem of graphs clustering”, Prikl. Diskr. Mat., 2022, no. 57, 91–97
18.	A. N. Rybalov, “The generic complexity of the graph triangulation problem”, Prikl. Diskr. Mat., 2022, no. 58, 105–111
19.	A. N. Rybalov, “Generic complexity of word problem in some semigroups”, Algebra and Logic, 61:6 (2022), 524–536
20.	A. Rybalov, “Generic complexity of algorithmic problems over Brandt semigroups”, Journal of Physics: Conference series, 1791 (2021), 1–10 (012085)
21.	A. Rybalov, “O genericheskoi slozhnosti problemy izomorfizma konechnykh polugrupp”, Prikladnaya diskretnaya matematika, 51 (2021), 120–128	1 ^[x]
22.	A. N. Rybalov, “On generic complexity of the isomorphism problem for finite semigroups”, Prikl. Diskr. Mat. Suppl., 2021, no. 14, 178–180
23.	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.
24.	A. Rybalov, “On generic complexity of theories of finite algebraic structures”, Journal of Physics: Conference series, 1901 (2021), 012046 , 7 pp.
25.	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.	1 ^[x]
26.	A. Rybalov, A. Shevlyakov, “Equationally extreme trees”, Journal of Physics: Conference series, 1901 (2021), 012048 , 7 pp.
27.	A. N. Rybalov, “The general complexity of the problem to recognize Hamiltonian paths”, Prikl. Diskr. Mat., 2021, no. 53, 120–126
28.	A. N. Rybalov, “On generic NP-completeness of the problem of Boolean circuits satisfiability”, Prikl. Diskr. Mat., 2020, no. 47, 101–107
29.	A. Rybalov, “A generic algorithm for the word problem in semigroups and groups”, Journal of Physics: Conference Series, 1546 (2020), 1–10 , 012100	1 ^[x]
30.	A. Rybalov, “A generic algorithm for the identity problem in finite groups and monoids”, Journal of Physics: Conference Series, 1546 (2020), 1–6 , 012101
31.	A. Rybalov, “O genericheskoi slozhnosti problemy predstavimosti naturalnykh chisel summoi dvukh kvadratov”, Prikladnaya diskretnaya matematika, 2020, no. 48, 93–99	4 ^[x]
32.	A. Rybalov, “Neplotnost genericheskoi m-svodimosti dlya rekursivno perechislimykh mnozhestv”, Vestnik Omskogo universiteta, 25:2 (2020), 9–12
33.	A. Rybalov, “O genericheskoi slozhnosti ekzistentsialnykh teorii”, Prikladnaya diskretnaya matematika, 2020, no. 49, 120–126	4 ^[x]
34.	A. Rybalov, “On the generic existential theory of finite graphs”, Siberian Elecronic Mathematical Reports, 17 (2020), 1710–1714
35.	A. Rybalov, “O genericheskoi slozhnosti problemy o summe podmnozhestv dlya polugrupp tselochislennykh matrits”, Prikladnaya diskretnaya matematika, 2020, no. 50, 118–126	1 ^[x]
36.	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
37.	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
38.	A. Rybalov, “O genericheskoi nerazreshimosti desyatoi problemy Gilberta dlya polinomialnykh derevev”, Prikladnaya diskretnaya matematika, 2019, no. 44, 107-112	4 ^[x]
39.	A. N. Rybalov, “On the generic complexity of the decoding problem for linear codes”, Prikl. Diskr. Mat. Suppl., 2019, no. 12, 198–202
40.	A. Rybalov, “Genericheskaya nerazreshimost universalnykh teorii”, Sibirskie elektronnye matematicheskie izvestiya, 16 (2019), 1289-1294
41.	A. Rybalov, “O slozhnosti ekzistentsialnoi i universalnoi teorii konechnykh polei”, Prikladnaya diskretnaya matematika, 2019, no. 45, 85-89	2 ^[x]
42.	A. Rybalov, “O genericheskoi slozhnosti problemy klasterizatsii grafov”, Prikladnaya diskretnaya matematika, 2019, no. 46, 72–77	6 ^[x]
43.	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
44.	A. N. Rybalov, “Relativized generic classes $\mathrm P$ and $\mathrm{NP}$”, Prikl. Diskr. Mat., 2018, no. 40, 100–104
45.	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
46.	A. N. Rybalov, “Generic amplification of recursively enumerable sets”, Algebra and Logic, 57:4 (2018), 289–294
47.	A. Rybalov, “A generic m-reducibility”, Lecture Notes in Computer Science, 10936 (2018), 359–364
48.	A. N. Rybalov, “On generic NP-completeness of the Boolean satisfiability problem”, Prikl. Diskr. Mat., 2017, no. 36, 106–112
49.	A. N. Rybalov, “Generic Kleene fixed point theorem”, Sib. Èlektron. Mat. Izv., 14 (2017), 732–736
50.	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
51.	A. N. Rybalov, “Generic Gödel's incompleteness theorem”, Algebra and Logic, 56:3 (2017), 232–235
52.	A. N. Rybalov, “On generic complexity of the problem of finding roots in groups of residues”, Prikl. Diskr. Mat., 2017, no. 38, 95–100
53.	A. Rybalov, “On the generic undecidability of the Halting Problem for normalized Turing machines”, Theory of Computing Systems, 60:4 (2017), 671-676	2 ^[x]
54.	A. Rybalov, “Generic hardness of the Boolean satisfiability problem”, Groups Complexity Cryptology, 9:2 (2017), 151-154
55.	A. N. Rybalov, “On generic complexity of the validity problem for Boolean formulas”, Prikl. Diskr. Mat., 2016, no. 2, 119–126
56.	A. N. Rybalov, “Generic undecidability of existential theory of integer numbers ring”, Sib. Èlektron. Mat. Izv., 13 (2016), 882–887
57.	A. N. Rybalov, “On generic complexity of the discrete logarithm problem”, Prikl. Diskr. Mat., 2016, no. 3, 93–97
58.	A. N. Rybalov, “A generic relation on recursively enumerable sets”, Algebra and Logic, 55:5 (2016), 387–393
59.	G. Noskov, A. Rybalov, “Generic case complexity of the Graph Isomorphism Problem”, Groups Complexity Cryptology, 8:1 (2016), 9-20
60.	A. N. Rybalov, “Generic incompleteness of formal arithmetic”, Sib. Èlektron. Mat. Izv., 12 (2015), 185–189
61.	A. N. Rybalov, “On generic complexity of the quadratic residuosity problem”, Prikl. Diskr. Mat., 2015, no. 2, 54–58
62.	A. Rybalov, “On the generic complexity of the searching graph isomorphism problem”, Groups Complexity Cryptology, 7:2 (2015), 191-194	4 ^[x]
63.	A. N. Rybalov, “On generic complexity of the quadratic residuosity problem”, Prikl. Diskr. Mat. Suppl., 2015, no. 8, 71–73
64.	Rybalov A., “Generic complexity of the Diophantine problem”, Groups Complexity Cryptology, 5:1 (2013) , 25–30 pp.	2 ^[x]
65.	A. Rybalov, “O genericheskoi nerazreshimosti Desyatoi problemy Gilberta”, Vestnik Omskogo universiteta, 2011, no. 4, 19-22
66.	A.N. Rybalov, “Generic complexity of first-order theories”, Siberian Elektronic Mathematical report, 8 (2011), 168–178
67.	A. Rybalov, “Generic Complexity of Presburger Arithmetic”, Theory of Computing Systems, 46:1 (2010), 2-8
68.	Rybalov A., “Polinomialnye klassy slozhnosti nad veschestvennymi algebrami s nilpotentnymi elementami”, Vestnik Omskogo universiteta, 2010, no. 4, 37-41
69.	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.
70.	A. Rybalov, A. Myasnikov, “Generic complexity of undecidable problems”, Journal of Symbolic Logic, 73:2 (2008), 656-673
71.	A. Rybalov, “On the strongly generic undecidability of the Halting Problem”, Theoretical Computer Science, 377 (2007), 268-270	11 ^[x]
72.	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	1 ^[x]
73.	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.
74.	A. Rybalov, “On the P–NP problem over real matrix rings”, Theoretical Computer Science, 314:1-2 (2004), 281–285	2 ^[x]
75.	Rybalov A. N., “Relativizations of the P=NP problem over the complex number field,”, Siberian Elektronic Mathematical report, 1 (2004), 91-98
76.	A. N. Rybalov, “Computational complexity in algebraic systems”, Siberian Math. J., 45:6 (2004), 1113–1123

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