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:	70 (70)
in MathSciNet:	15 (15)
in zbMATH:	14 (14)
in Web of Science:	47 (47)
in Scopus:	39 (39)
Cited articles:	33
Citations:	100
Presentations:	1

Number of views:
This page:	1935
Abstract pages:	6556
Full texts:	2166
References:	1213

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

List of publications on ZentralBlatt

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

Full 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

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

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

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

2020
22.	A. N. Rybalov, “On generic NP-completeness of the problem of Boolean circuits satisfiability”, Prikl. Diskr. Mat., 2020, no. 47, 101–107
23.	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]
24.	A. Rybalov, “A generic algorithm for the identity problem in finite groups and monoids”, Journal of Physics: Conference Series, 1546 (2020), 1–6 , 012101
25.	A. Rybalov, “O genericheskoi slozhnosti problemy predstavimosti naturalnykh chisel summoi dvukh kvadratov”, Prikladnaya diskretnaya matematika, 2020, no. 48, 93–99	4 ^[x]
26.	A. Rybalov, “Neplotnost genericheskoi m-svodimosti dlya rekursivno perechislimykh mnozhestv”, Vestnik Omskogo universiteta, 25:2 (2020), 9–12
27.	A. Rybalov, “O genericheskoi slozhnosti ekzistentsialnykh teorii”, Prikladnaya diskretnaya matematika, 2020, no. 49, 120–126	4 ^[x]
28.	A. Rybalov, “On the generic existential theory of finite graphs”, Siberian Elecronic Mathematical Reports, 17 (2020), 1710–1714
29.	A. Rybalov, “O genericheskoi slozhnosti problemy o summe podmnozhestv dlya polugrupp tselochislennykh matrits”, Prikladnaya diskretnaya matematika, 2020, no. 50, 118–126	1 ^[x]
30.	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
31.	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
32.	A. Rybalov, “O genericheskoi nerazreshimosti desyatoi problemy Gilberta dlya polinomialnykh derevev”, Prikladnaya diskretnaya matematika, 2019, no. 44, 107-112	4 ^[x]
33.	A. N. Rybalov, “On the generic complexity of the decoding problem for linear codes”, Prikl. Diskr. Mat. Suppl., 2019, no. 12, 198–202
34.	A. Rybalov, “Genericheskaya nerazreshimost universalnykh teorii”, Sibirskie elektronnye matematicheskie izvestiya, 16 (2019), 1289-1294
35.	A. Rybalov, “O slozhnosti ekzistentsialnoi i universalnoi teorii konechnykh polei”, Prikladnaya diskretnaya matematika, 2019, no. 45, 85-89	2 ^[x]
36.	A. Rybalov, “O genericheskoi slozhnosti problemy klasterizatsii grafov”, Prikladnaya diskretnaya matematika, 2019, no. 46, 72–77	6 ^[x]

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

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

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

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

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

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

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

2009
63.	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
64.	A. Rybalov, A. Myasnikov, “Generic complexity of undecidable problems”, Journal of Symbolic Logic, 73:2 (2008), 656-673

2007
65.	A. Rybalov, “On the strongly generic undecidability of the Halting Problem”, Theoretical Computer Science, 377 (2007), 268-270	11 ^[x]
66.	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
67.	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
68.	A. Rybalov, “On the P–NP problem over real matrix rings”, Theoretical Computer Science, 314:1-2 (2004), 281–285	2 ^[x]
69.	Rybalov A. N., “Relativizations of the P=NP problem over the complex number field,”, Siberian Elektronic Mathematical report, 1 (2004), 91-98
70.	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