Geodesic
The general complexity of the problem to recognize Hamiltonian paths
Prikladnaâ diskretnaâ matematika, no. 3 (2021), pp. 120-126
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Generic-case approach to algorithmic problems has been offered by A. Miasnikov, V. Kapovich, P. Schupp, and V. Shpilrain in 2003. This approach studies an algorithm behavior on typical (almost all) inputs and ignores the rest of inputs. In this paper, we study the generic complexity of the problem of recognition of Hamiltonian paths in finite graphs. A path in graph is called Hamiltonian if it passes through all vertices exactly once. We prove that under the conditions $\text {P} \neq \text{NP}$ and $\text{P} = \text{BPP}$ for this problem there is no polynomial strongly generic algorithm. A strongly generic algorithm solves a problem not on the whole set of inputs, but on a subset, the sequence of frequencies of which exponentially quickly converges to $1$ with increasing size. To prove the theorem, we use the method of generic amplification, which allows to construct generically hard problems from the problems hard in the classical sense. The main component of this method is the cloning technique, which combines the inputs of a problem together into sufficiently large sets of equivalent inputs. Equivalence is understood in the sense that the problem is solved similarly for them.
Keywords: generic complexity, Hamiltonian path. 
@article{PDM_2021_3_a7,
     author = {A. N. Rybalov},
     title = {The general complexity of the problem {to~recognize~Hamiltonian} paths},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {120--126},
     year = {2021},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2021_3_a7/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - The general complexity of the problem to recognize Hamiltonian paths
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2021
SP  - 120
EP  - 126
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/PDM_2021_3_a7/
LA  - ru
ID  - PDM_2021_3_a7
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T The general complexity of the problem to recognize Hamiltonian paths
%J Prikladnaâ diskretnaâ matematika
%D 2021
%P 120-126
%N 3
%U http://geodesic.mathdoc.fr/item/PDM_2021_3_a7/
%G ru
%F PDM_2021_3_a7
A. N. Rybalov. The general complexity of the problem to recognize Hamiltonian paths. Prikladnaâ diskretnaâ matematika, no. 3 (2021), pp. 120-126. http://geodesic.mathdoc.fr/item/PDM_2021_3_a7/

[1] Karp R., “Reducibility among combinatorial problems”, Complexity of Computer Computations, The IBM Research Symposia Ser., eds. R. E. Miller, J. W. Thather, 1972, 85–103 | Zbl

[2] Impagliazzo R., Wigderson A., “P $=$ BPP unless E has subexponential circuits: Derandomizing the XOR Lemma”, Proc. 29th STOC, ACM, El Paso, 1997, 220–229

[3] Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | Zbl

[4] Gimadi E.H., Glebov N.I., Perepelitsa V.A., “Algorithms with bounds for problems of discrete optimization”, Problemy Kibernetiki, 31 (1975), 35–42 (in Russian)

[5] Rybalov A., “On generic complexity of the validity problem for Boolean formulas”, Prikladnaya Diskretnaya Matematika, 2016, no. 2(32), 119–126 (in Russian) | Zbl

[6] Perepelitsa V.A., “On two problems from graph theory”, Doklady AN SSSR, 194:6 (1970), 1269–1272 (in Russian)

[7] Posa L., “Hamiltonian circuits in random graphs”, Discrete Math., 14 (1976), 359–364 | DOI | Zbl