Взаимоотношения между сложностными классами P, NP и NPC

Известно [1, 878], что класс полиномиальных проблем был определен в 1964 году Кобэмом и независимо в 1965 году Эдмондсом. Эдмондс определил также класс NP и высказал гипотезу P≠NP. В той форме, в которой эти понятия вводились указанными авторами, мы их использовали в нашей работе [2], где, в частности, было указано, что определение класса NP имеет ограничение на длину сертификата, формируемого проверяющим алгоритмом, по-видимому, вызванное алгоритмом проверки правильности решения классической алгебраической задачи решения алгебраического уравнения. Общеизвестно, что если х0 решение алгебраического уравнения p(х)=0 где p(x)является полиномом от x с целыми коэффициентами, то проверка правильности решения х0 есть равенство p(x0)=0. Очевидно, если решение х0 отыскивается за полиномиальное число шагов, то и проверка правильности его осуществляется за полиномиальное число шагов. Разумеется, способ проверки правильности решения задачи зависит от специфики задачи.

Есть проблемы, которые не имеют решений, а значит, и не могут быть проверены, хотя сертификаты для проверки правильности решения и существуют. Например, в тридцатых годах 19 века Галуа удалось доказать [3, 240], что для всякого n≥5 можно указать неразрешимые в радикалах уравнения n-й степени с целочисленными коэффициентами.

Естественно при данном Эдмондсом определении класса NP любая полиномиальная проблема принадлежит NP, так как композиция полиномов является полиномом. Но если ограничение на сертификат при проверке правильности решения задачи убрать, что вполне объяснимо, так как способ проверки зависит как от характера решаемой задачи, так и от свойства решения, правильность которого проверяется. При рассмотрении той или иной проблемы, если нас интересует не только решение ее, а и проверка правильности решения, то решение проблемы обычно считается прямой задачей, а проверка правильности решения проблемы - обратной. При создании криптосистемы отыскание шифра представляет собой прямую задачу, а расшифровка обратную. Поэтому очень важно в криптографической системе, чтобы расшифровка была алгоритмически сложнее, чем отыскание шифра. В такой интерпретации криптографической системы и заключается решение проблемы С. А. Кука, предложенной институтом Клея среди семи проблем тысячелетия, которое было нами представлено в работах [2] [4-7].

В 1971 году С. А. Кук [8] в классе NP выделил подкласс самых трудных проблем, так называемых NPC (NP-полных) проблем и доказал NP–полноту двух конкретных проблем. Независимо понятие NP-полноты ввел также Л. А. Левин [9], который также доказал NP-полноту нескольких проблем. С этих пор многими авторами доказана NP-полнота тысяч проблем, однако сложностная природа их официально не выяснена. Согласно определению NP-полной проблемы [1, 851], если некоторая NP-полная проблема полиномиальная, то все NP-полные проблемы являются полиномиальными и наоборот, если некоторая NP-полная проблема не является полиномиальной, то и все NP-полные проблемы не являются полиномиальными. В [10] мы построили одну NP-полную проблему, которая не является полиномиальной. Таким образом, мы доказали, что все NP-полные проблемы не являются полиномиальными. В работе [11] мы построили алгоритм для решения одной проблемы из перечислительной комбираторики, из которого следуют теорема, доставляющая критерий полиномиальности сформулированной проблемы и следствие 2 о том, что все NP-полные проблемы не являются полиномиальными.

В заключение отметим, что проблема P=NP, которую пытаются решить авторы [12], в природе не существует, так как мы доказали справедливость гипотезы Эдмондса P≠NP двумя способами: с одной стороны, мы показали конструктивно существование полиномиальных проблем, проверка правильности решения которых требует неполиномиальное число шагов, что очень важно в криптографии; с другой стороны, мы доказали, что NP-полные проблемы не являются полиномиальными.

Литература

1. Сormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms. Cambridge, Massachusetts London, England The MIT Press, 1990. 960 p.
2. Кочкарев Б. С. Доказательство гипотезы Эдмондса и решение проблемы Кука. Наука, техника и образование. 2014 № 2 с. 6-9.
3. Курош А. Г. Курс высшей алгебры. Государственное издательство физико-математической литературы. Москва 1962. 432 с.
4. Kochkarev B. S. On Cook’s problem, http: //www.math.nsc.ru/conference/malmeet/08/Abs.
5. Кочкарев Б. С. - Приложение монотонных функций алгебры логики к проблеме Кука. Тезисы докладов Международной научно-образовательной конференции. / РУДН. Москва, 2009. 274-275 с.
6. Кочкарев Б. С. - К проблеме Кука. // Математическое образование в школе и в Вузе в условиях перехода на новые образовательные стандарты: Материалы Всероссийской научно-практической конференции с международным участием. / ЕГГПУ. Казань. 2010. 133-136 с.
7. KochkarevB.S. - About one class polynomial problems with not polynomial certificates. Second International Conference «Cluster Computing» CC 2013 (Ukraine. Lviv. June 3-5. 2013) p. 99-100.
8. Cook S. A. - The complexity of theorem proving procedures. // In Proccedings of the Third Annual ACM Symposium on Theory of Computing, P. 151-158, 1971.
9. Levin L. A. - Universal sorting problems. // Problemy Peredachi Informatsii. 9 (3), c. 265-266, 1973.
10. Kochkarev B. S. Proof of the hypothesis Edmonds’s, not polynomial of NPC problems and classification of the problems with polynomial certificates. // arxiv: 1303.2580v1 [cs.CC] 7 Mar 2013.
11. Кочкарев Б. С. - Об одном алгоритме, не согласующемся с тезисами Тьюринга, Черча и Маркова. Проблемы современной науки и образования. 2014. № 3 (21) с. 23-25.
12. Razborov A. A., Rudich S. Natural proof. Proceedings of the 26 th Annual ACM Symposium on the Theory of Computing. P. 204-213. DOI:10.1145/195058.195134.

Публикация научной статьи. Пошаговая инструкция

Есть вопрос? Задайте его Вашему персональному менеджеру. Служба поддержки призвана помочь пользователям в решении любых проблем, связанных с вопросами публикации своих работ и другими аспектами работы издательства «Проблемы науки».