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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Взаимоотношения между сложностными классами P, NP и NPC
Кочкарев Б. С.
Кочкарев Баграм Сибгатуллович /Kochkarev Bagram Sibgatullovich — кандидат физико-математических наук, доцент, кафедра высшей математики и математического моделирования,
Институт математики и механики имени Н. И. Лобачевского Казанский (Приволжский) федеральный университет, г. Казань
Аннотация: в теории алгоритмов в определении класса NP, введенного Жаком Эдмондсом, имеется ограничение на длину сертификата, формируемого проверяющим алгоритмом. В связи с этим любая полиномиальная проблема принадлежит классу NP. Однако если это ограничение снять, то мы конструктивно показываем существование полиномиальных проблем, которые не принадлежат NP. С другой стороны, даже при указанном ограничении в определении класса NP, мы доказываем справедливость гипотезы Ж. Эдмондса P ф NP, именно, все NP-полные проблемы не являются полиномиальными.
Abstract: in the theory of algorithms in a class of NP introduced by J. Edmonds has a limit on the length of the inspection certificate generated by the algorithm. In this respect, any polynomial problem belongs to NP. However, if you remove this limitation, we constructively show the existence of polynomial problems that do not belong to the NP. On the other hand, even with the limitation specified in the definition of NP, we prove the conjecture J. Edmonds P Ф NP, namely, all the NP-complete problems are nonpolynomial.
Ключевые слова: класс полиномиальных проблем P, класс проблем NP, класс NP-полных проблем.
Keywords: class of the polynomial problems P, class of the NP problems, class of the NPC problems.
Известно [1, 878], что класс полиномиальных проблем был определен в 1964 году Кобэмом и независимо в 1965 году Эдмондсом. Эдмондс определил также класс NP и высказал гипотезу P Ф NP. В той форме, в которой эти понятия вводились указанными авторами, мы их использовали в нашей работе [2], где, в частности, было указано, что определение класса NP имеет ограничение на длину сертификата, формируемого проверяющим алгоритмом, по-видимому, вызванное алгоритмом проверки правильности решения классической алгебраической задачи решения алгебраического уравнения. Общеизвестно, что если Х0 решение алгебраического уравнения р (х) = 0, где р (х) является полиномом от х с целыми
коэффициентами, то проверка правильности решения Х0 есть равенство р (Х0) = 0. Очевидно, если решение Х отыскивается за полиномиальное число шагов, то и проверка правильности его осуществляется
за полиномиальное число шагов. Разумеется, способ проверки правильности решения задачи зависит от специфики задачи.
Есть проблемы, которые не имеют решений, а значит, и не могут быть проверены, хотя сертификаты для проверки правильности решения и существуют. Например, в тридцатых годах 19 века Галуа удалось доказать [3, 240], что для всякого n & gt- 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. Cormen 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. Kochkarev B. 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/195 058. 195 134.

ПоказатьСвернуть
Заполнить форму текущей работой