Candidate of Physical and Mathematical Sciences, Associate Professor of the Department 604, Aerospace Faculty
кандидат физико-математических наук, доцент кафедры 604, аэрокосмический факультет
The article is devoted to a rigorous proof of the first millennium problem, which is named as P≠NP. This problem was raised in 1971 by S. Cook and marked the beginning of a long struggle in order to understand and prove it. The problem is closely related to the concept of a combinatorial explosion, which concept was aroused in the early 1970s and became a symbol of the enormous difficulties that developers of algorithms and programs have to face, since the complexity of the tasks that have to be solved is growing every day. The presented proof is based on the achievements of graph theory and algorithm theory. Necessary conditions (normalizing), to which arbitrary algorithm must satisfy in order to be solved with a help of a Turing machine, are proved in the article. Further, using the theory of algorithms and graph theory, it is proved that normalized (necessary condition) graphs (visualization of algorithms) with respect to such a characteristic of their complexity as a cyclomatic number fall into three non-intersecting sets that have different properties. These properties are determined by the structural features of graphs, and they can be taken into account when developing algorithms and programs for solving mass problems. The division of algorithms of mass problems into three non-intersecting sets is proved. Such division corresponds with graph-schemes, or block-schemes of polynomial (P) or enumeration (NP) algorithms. This proves a sufficient condition, to which algorithms must satisfy in order to belong to different classes and actually confirm that P≠NP.
Представлено строгое доказательство первой проблемы миллениума, а именно: P≠NP, которая была озвучена в 1971 г. в статье Стивена Кука и положила начало долгой борьбе за ее осмысление и доказательство. Проблема тесно связана с понятием комбинаторного взрыва, возникшего в начале 1970-х гг. Она стала символом тех громадных трудностей, с которыми приходится сталкиваться разработчикам алгоритмов и программ, поскольку сложность решаемых задач с каждым днем растет. Предлагаемое доказательство основано на достижениях теории графов и теории алгоритмов. Обосновывается необходимое условие того, чтобы произвольный алгоритм мог быть решен с помощью машины Тьюринга и приводятся необходимые теоремы. Далее с помощью теории алгоритмов и теории графов доказывается, что нормализованные графы (визуализации алгоритмов) относительно такой характеристики их сложности, как цикломатическое число, распадаются на три непересекающихся множества, которые обладают различными свойствами. Эти свойства определяются структурными особенностями графов, их можно учесть при разработке алгоритмов и программ для решения массовых задач. Доказывается разделение алгоритмов массовых задач на непересекающиеся множества, которые соответствуют граф-схемам (блок-схемам) полиномиальных (P) или переборных (NP) алгоритмов. Этим обосновывается достаточное условие, которое, собственно, и подтверждает, что P≠NP.