In this paper the probabilistic method is presented for solving the minimum vertex cover problem using systems of non-linear equations that are formed on the basis of a neighborhood relationship of a particular vertex of a given graph. The minimum vertex cover problem is one of the classic mathematical optimization problems that have been shown to be NP-hard. It has a lot of real-world applications in different fields of science and technology. This study finds solutions to this problem by means of the two basic procedures. In the first procedure three probabilistic pairs of variables according to the maximum vertex degree are formed and processed accordingly. The second procedure checks a given graph for the presence of the leaf vertices. Special software package to check the validity of these procedures was written. The experiment results show that our method has significantly better time complexity and much smaller frequency of the approximation errors in comparison with one of the most currently efficient algorithms.

It is shown an incorrectness of introduction of a class of NP-complete problems, which reason is that Cook’s S.А. theorem on that the “satisfiability” problem is the universal NP-complete problem, is not true and, therefore, the issue on existence of at least one NP-complete problem remains open, that explains failures of attempts to estimate correlations between P and NP classes.