We show the results of a statistical study of the complexity of the asymmetric traveling
salesman problem (ATSP) obtained by processing a specially generated pool of matrices.
We show that the normal distribution can serve as an approximation to the distribution of the
logarithm of complexity for a fixed problem dimension. We construct a family of probability
distributions that represent satisfactory approximations of the complexity distribution with a
dimension of the cost matrix from 20 to 49. Our main objective is to make probabilistic predictions
of the complexity of individual problems for larger values of the dimension of the cost
matrix. We propose a representation of the complexity distribution that makes it possible to
predict the complexity. We formulate the unification hypothesis and show directions for further
study, in particular proposals on the task of clustering “complex” and “simple” ATSP problems
and proposals on the task of directly predicting the complexity of a specific problem instance
based on the initial cost matrix.