Математическая логика и теория алгоритмов

§ 5. iVjP-полные и iVP-трудные задачи Рассмотрим сводимость задач. Хотя сведение одних задач к другим является традиционной математической деятельностью, оно до работ С. Кука не было подвержено самостоятельному исследова­ нию. Именно С, Куку принадлежит честь выделения этого понятия как центрального в теории полиномиальной сводимости. Говорят, что задача Zi сводится к задаче 2^, если метод решения задачи Та можно преобразовать в метод решения задачи Zi, Своди­ мость называется полиномиальной, если указанное преобразование можно осуществить за полиномиальное время. Если одновременно задача 2\ полиномиально сводится к задаче Ъх и полиномиально сводится к задаче 2\, то задачи 2\ и Z2 пол номиально эквивалентны. Задача называется NP-трудной, если каждая задача из NP п номиально сводится к ней. Л'Р-трудная задача имеет тот смысл, что эта задача не проще, чем «самая трудная в NP ». В классе NP выделяются 7*/Р-полные задачи. Задача называется NP-полной, если она входит в NP и каждая задача из NP полином но сводится к ней (т.е. является Л'Р-трудной). iVP-полные задачи понимаются как самые трудные задачи нз класса NP. Класс NP- полных задач обладает следующими свойствами. 1, Никакую ЛФ-полную задачу нельзя решить никаким извест­ ным полиномиальным алгоритмом, несмотря на настойчивые усилия многих блестящих исследователей. 2. Если бы удалось построить полиномиальный алгоритм для какой-нибудь iVP-полиой задачи, то это бы означало полиномиальную разрешимость каждой Л'Р-полной задачи. Основываясь на этих двух свойствах, многие высказывают ги­ потезу, что Р ^ NP. Практическое значение понятия iVP-полной задачи лежит именно в широко распространенном мнении, что такие задачи по существу труднорешаемы. Следовательно, при их решении в худ­ 289