Необходимые и достаточные условия разделения структур алгоритмов на непересекающиеся множества: полиномиальные и переборные алгоритмы

Представлено строгое доказательство первой проблемы миллениума, а именно: P≠NP, которая была озвучена в 1971 г. в статье Стивена Кука и положила начало долгой борьбе за ее осмысление и доказательство. Проблема тесно связана с понятием комбинаторного взрыва, возникшего в начале 1970-х гг. Она стала символом тех громадных трудностей, с которыми приходится сталкиваться разработчикам алгоритмов и программ, поскольку сложность решаемых задач с каждым днем растет. Предлагаемое доказательство основано на достижениях теории графов и теории алгоритмов. Обосновывается необходимое условие того, чтобы произвольный алгоритм мог быть решен с помощью машины Тьюринга и приводятся необходимые теоремы. Далее с помощью теории алгоритмов и теории графов доказывается, что нормализованные графы (визуализации алгоритмов) относительно такой характеристики их сложности, как цикломатическое число, распадаются на три непересекающихся множества, которые обладают различными свойствами. Эти свойства определяются структурными особенностями графов, их можно учесть при разработке алгоритмов и программ для решения массовых задач. Доказывается разделение алгоритмов массовых задач на непересекающиеся множества, которые соответствуют граф-схемам (блок-схемам) полиномиальных (P) или переборных (NP) алгоритмов. Этим обосновывается достаточное условие, которое, собственно, и подтверждает, что P≠NP.