The general complexity of the problem to~recognize~Hamiltonian paths

A. N. Rybalov

Prikladnaâ diskretnaâ matematika, no. 3 (2021), pp. 120-126

Résumé

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.

Détail

Keywords: generic complexity, Hamiltonian path.