|
|
|
|
References
|
|
| |
| 1. |
Garey M. and Johnson D., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979, 340 pp.  |
| 2. |
Kapovich I., Miasnikov A., Schupp P., and Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694  |
| 3. |
Gimadi E. H., Glebov N. I., and Perepelitsa V. A., “Algorithms with bounds for problems of discrete optimization”, Problemy Kibernetiki, 31 (1975), 35–42 (in Russian) |
| 4. |
Blum M., “How to prove a theorem so no one else can claim it”, Proc. Intern. Congress Math. (Berkeley, CA, 1986), 1444–1451 |
| 5. |
Myasnikov A. G. and Rybalov A. N., “Generic complexity of undecidable problems”, J. Symbolic Logic, 73:2 (2008), 656–673 |
| 6. |
Rybalov A. N., “On the strongly generic undecidability of the Halting Problem”, Theor. Comput. Sci., 377 (2007), 268–270 |
| 7. |
Rybalov A. N., “Generic complexity of Presburger arithmetic”, Theory Comput. Systems, 46:1 (2010), 2–8 |
| 8. |
Rybalov A. N., “Generic complexity of the Diophantine problem”, Groups Complexity Cryptology, 5:1 (2013), 25–30 |
| 9. |
Rybalov A. N., “Generic hardness of the Boolean satisfiability problem”, Groups Complexity Cryptology, 9:2 (2017), 151–154  |
| 10. |
Rybalov A. N., “On generic complexity of the graph clustering problem”, Prikladnaya Diskretnaya Matematika, 2019, no. 46, 72–77 (in Russian)  |
| 11. |
Rybalov A. N., “The general complexity of the problem to recognize Hamiltonian paths”, Prikladnaya Diskretnaya Matematika, 2021, no. 53, 120–126 (in Russian) |
| 12. |
Impagliazzo R. and Wigderson A., “P $=$ BPP unless E has subexponential circuits: Derandomizing the XOR Lemma”, Proc. 29th STOC, ACM, El Paso, 1997, 220–229 |
| 13. |
Rybalov A. N., “On generic complexity of the validity problem for Boolean formulas”, Prikladnaya Diskretnaya Matematika, 2016, no. 2(32), 119–126 (in Russian) |
