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

Total publications:	71 (71)
in MathSciNet:	15 (15)
in zbMATH:	14 (14)
in Web of Science:	47 (47)
in Scopus:	39 (39)
Cited articles:	34
Citations:	106
Presentations:	1

Number of views:
This page:	2171
Abstract pages:	7941
Full texts:	2668
References:	1599

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

by years

by types

by times cited

common list

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


2024
1.	Rybalov A., “O slozhnosti problemy ravenstva v polugruppakh s usloviem odnorodnosti opredelyayuschikh sootnoshenii”, Sibirskie elektronnye matematicheskie izvestiya, 21:1 (2024), 55–61
2.	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}$
3.	Rybalov A., “Genericheski nerazreshimye i trudnorazreshimye problemy”, Prikladnaya diskretnaya matematika, 2024, no. 63, 109–116
4.	Rybalov A., “O genericheskoi slozhnosti resheniya uravnenii nad naturalnymi chislami so slozheniem”, Prikladnaya diskretnaya matematika, 2024, no. 64, 72–78
5.	Rybalov A., “O genericheskoi slozhnosti problemy vychisleniya funktsii Eilera”, Prikladnaya diskretnaya matematika, 2024, no. 65, 110–117
6.	Rybalov A., “O genericheskoi slozhnosti problemy diskretnogo logarifma v posledovatelnostyakh Lyuka”, Prikladnaya diskretnaya matematika, 2024, no. 66, 116–122

2023
7.	Rybalov A., “Genericheskie polinomialnye algoritmy dlya problemy o ryukzake v nekotorykh matrichnykh polugruppakh”, Sibirskie elektronnye matematicheskie izvestiya, 20:1 (2023), 100–109
8.	Rybalov A., “O genericheskoi slozhnosti problemy klasterizatsii grafov s ogranicheniyami na razmer klasterov”, Prikladnaya diskretnaya matematika, 2023, no. 60, 114–119
9.	Rybalov A., “O genericheskoi slozhnosti problemy faktorizatsii tselykh chisel”, Prikladnaya diskretnaya matematika, 2023, no. 61, 121–126
10.	Rybalov A., “O genericheskoi slozhnosti problemy izvlecheniya kvadratnogo kornya po prostomu modulyu”, Prikladnaya diskretnaya matematika, 2023, no. 62, 119–123

2022
11.	A. N. Rybalov, “Generic complexity of the membership problem for semigroups of integer matrices”, Prikl. Diskr. Mat., 2022, no. 55, 95–101
12.	A. N. Rybalov, “The generic complexity of the bounded problem of graphs clustering”, Prikl. Diskr. Mat., 2022, no. 57, 91–97
13.	A. N. Rybalov, “The generic complexity of the graph triangulation problem”, Prikl. Diskr. Mat., 2022, no. 58, 105–111
14.	Rybalov A., “O genericheskoi slozhnosti problemy ravenstva v nekotorykh polugruppakh”, Algebra i logika, 61:6 (2022), 766–783

2021
15.	A. Rybalov, “Generic complexity of algorithmic problems over Brandt semigroups”, Journal of Physics: Conference series, 1791 (2021), 1–10 (012085)
16.	A. Rybalov, “O genericheskoi slozhnosti problemy izomorfizma konechnykh polugrupp”, Prikladnaya diskretnaya matematika, 51 (2021), 120–128	1 ^[x]
17.	A. N. Rybalov, “On generic complexity of the isomorphism problem for finite semigroups”, Prikl. Diskr. Mat. Suppl., 2021, no. 14, 178–180
18.	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.
19.	A. Rybalov, “On generic complexity of theories of finite algebraic structures”, Journal of Physics: Conference series, 1901 (2021), 012046 , 7 pp.
20.	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]
21.	A. Rybalov, A. Shevlyakov, “Equationally extreme trees”, Journal of Physics: Conference series, 1901 (2021), 012048 , 7 pp.
22.	A. N. Rybalov, “The general complexity of the problem to recognize Hamiltonian paths”, Prikl. Diskr. Mat., 2021, no. 53, 120–126

2020
23.	A. N. Rybalov, “On generic NP-completeness of the problem of Boolean circuits satisfiability”, Prikl. Diskr. Mat., 2020, no. 47, 101–107
24.	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]
25.	A. Rybalov, “A generic algorithm for the identity problem in finite groups and monoids”, Journal of Physics: Conference Series, 1546 (2020), 1–6 , 012101
26.	A. Rybalov, “O genericheskoi slozhnosti problemy predstavimosti naturalnykh chisel summoi dvukh kvadratov”, Prikladnaya diskretnaya matematika, 2020, no. 48, 93–99	4 ^[x]
27.	A. Rybalov, “Neplotnost genericheskoi m-svodimosti dlya rekursivno perechislimykh mnozhestv”, Vestnik Omskogo universiteta, 25:2 (2020), 9–12
28.	A. Rybalov, “O genericheskoi slozhnosti ekzistentsialnykh teorii”, Prikladnaya diskretnaya matematika, 2020, no. 49, 120–126	4 ^[x]
29.	A. Rybalov, “On the generic existential theory of finite graphs”, Siberian Elecronic Mathematical Reports, 17 (2020), 1710–1714
30.	A. Rybalov, “O genericheskoi slozhnosti problemy o summe podmnozhestv dlya polugrupp tselochislennykh matrits”, Prikladnaya diskretnaya matematika, 2020, no. 50, 118–126	1 ^[x]
31.	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
32.	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

2019
33.	A. Rybalov, “O genericheskoi nerazreshimosti desyatoi problemy Gilberta dlya polinomialnykh derevev”, Prikladnaya diskretnaya matematika, 2019, no. 44, 107-112	4 ^[x]
34.	A. N. Rybalov, “On the generic complexity of the decoding problem for linear codes”, Prikl. Diskr. Mat. Suppl., 2019, no. 12, 198–202
35.	A. Rybalov, “Genericheskaya nerazreshimost universalnykh teorii”, Sibirskie elektronnye matematicheskie izvestiya, 16 (2019), 1289-1294
36.	A. Rybalov, “O slozhnosti ekzistentsialnoi i universalnoi teorii konechnykh polei”, Prikladnaya diskretnaya matematika, 2019, no. 45, 85-89	2 ^[x]
37.	A. Rybalov, “O genericheskoi slozhnosti problemy klasterizatsii grafov”, Prikladnaya diskretnaya matematika, 2019, no. 46, 72–77	6 ^[x]

2018
38.	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
39.	A. N. Rybalov, “Relativized generic classes $\mathrm P$ and $\mathrm{NP}$”, Prikl. Diskr. Mat., 2018, no. 40, 100–104
40.	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
41.	A. N. Rybalov, “Generic amplification of recursively enumerable sets”, Algebra and Logic, 57:4 (2018), 289–294
42.	A. Rybalov, “A generic m-reducibility”, Lecture Notes in Computer Science, 10936 (2018), 359–364

2017
43.	A. N. Rybalov, “On generic NP-completeness of the Boolean satisfiability problem”, Prikl. Diskr. Mat., 2017, no. 36, 106–112
44.	A. N. Rybalov, “Generic Kleene fixed point theorem”, Sib. Èlektron. Mat. Izv., 14 (2017), 732–736
45.	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
46.	A. N. Rybalov, “Generic Gödel's incompleteness theorem”, Algebra and Logic, 56:3 (2017), 232–235
47.	A. N. Rybalov, “On generic complexity of the problem of finding roots in groups of residues”, Prikl. Diskr. Mat., 2017, no. 38, 95–100
48.	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]
49.	A. Rybalov, “Generic hardness of the Boolean satisfiability problem”, Groups Complexity Cryptology, 9:2 (2017), 151-154

2016
50.	A. N. Rybalov, “On generic complexity of the validity problem for Boolean formulas”, Prikl. Diskr. Mat., 2016, no. 2, 119–126
51.	A. N. Rybalov, “Generic undecidability of existential theory of integer numbers ring”, Sib. Èlektron. Mat. Izv., 13 (2016), 882–887
52.	A. N. Rybalov, “On generic complexity of the discrete logarithm problem”, Prikl. Diskr. Mat., 2016, no. 3, 93–97
53.	A. N. Rybalov, “A generic relation on recursively enumerable sets”, Algebra and Logic, 55:5 (2016), 387–393
54.	G. Noskov, A. Rybalov, “Generic case complexity of the Graph Isomorphism Problem”, Groups Complexity Cryptology, 8:1 (2016), 9-20

2015
55.	A. N. Rybalov, “Generic incompleteness of formal arithmetic”, Sib. Èlektron. Mat. Izv., 12 (2015), 185–189
56.	A. N. Rybalov, “On generic complexity of the quadratic residuosity problem”, Prikl. Diskr. Mat., 2015, no. 2, 54–58
57.	A. Rybalov, “On the generic complexity of the searching graph isomorphism problem”, Groups Complexity Cryptology, 7:2 (2015), 191-194	3 ^[x]
58.	A. N. Rybalov, “On generic complexity of the quadratic residuosity problem”, Prikl. Diskr. Mat. Suppl., 2015, no. 8, 71–73

2013
59.	Rybalov A., “Generic complexity of the Diophantine problem”, Groups Complexity Cryptology, 5:1 (2013) , 25–30 pp.	2 ^[x]

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

2010
62.	A. Rybalov, “Generic Complexity of Presburger Arithmetic”, Theory of Computing Systems, 46:1 (2010), 2-8
63.	Rybalov A., “Polinomialnye klassy slozhnosti nad veschestvennymi algebrami s nilpotentnymi elementami”, Vestnik Omskogo universiteta, 2010, no. 4, 37-41

2009
64.	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.

2008
65.	A. Rybalov, A. Myasnikov, “Generic complexity of undecidable problems”, Journal of Symbolic Logic, 73:2 (2008), 656-673

2007
66.	A. Rybalov, “On the strongly generic undecidability of the Halting Problem”, Theoretical Computer Science, 377 (2007), 268-270	11 ^[x]
67.	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]

2005
68.	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.

2004
69.	A. Rybalov, “On the P–NP problem over real matrix rings”, Theoretical Computer Science, 314:1-2 (2004), 281–285	2 ^[x]
70.	Rybalov A. N., “Relativizations of the P=NP problem over the complex number field,”, Siberian Elektronic Mathematical report, 1 (2004), 91-98
71.	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

Registration to the website

Logotypes