Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Л^Р-трудная задача имеет тот смысл, что эта задача не проще, чем «самая трудная в NP » . В классе NP выделяются iVP-полные задачи. Задача называется NP-полной, если она входит в NP и каждая задача из NP полиномиально сводится к ней (т.е. является ТУР-трудной). ЛТ'-полные задачи понимаются как самые трудные задачи из класса NP. Класс NP- полных задач обладает следующими свойствами. 1. Никакую Л^Р-полную задачу нельзя решить никаким известным полино­ миальным алгоритмом, несмотря на настойчивые усилия многих блестящих ис­ следователей. 2. Если бы удалось построить полиномиальный алгоритм для какой-нибудь Л^Р-полной задачи, то это бы означало полиномиальную разрешимость каждой iVP-полной задачи. Основываясь на этих двух свойствах, многие высказывают гипотезу, что Практическое значение понятия iVP-полной задачи лежит именно в ши­ роко распространенном мнении, что такие задачи по существу труднорешаемы. Следовательно, при их решении в худшем случае потребуется экспоненциаль­ ное количество времени и не будет возможности решить на практике такие за­ дачи, за исключением очень малого числа индивидуальных задач. Первой зада­ чей, для которой было доказано, что она является Л^Р-полной, была проблема о выполнимости (см. задачу 1 в § 4). Имеет место следующая теорема. Теорема 7.1 (теорема Кука). Задача выяснения выполнимости формулы логики высказываний является Л^Р-полной. Вторым примером ТУР-полной задачи можно отметить задачу выяснения гамильтоновости графа. Если дана последовательность вершин графа, то легко убедиться будет ли эта последовательность образовывать гамильтоновый цикл, т.е. предполагаемое решение легко проверить. Рассмотрим Рис. 7.3 взятый из [18]. На Рис 7.3 а) жирными линиями указан цикл, который является гамильто- новым. Если этот цикл не предъявлен, то выяснить гамильтоновость графа представляет собой нетривиальную задачу, см. например Рис. 7.3 б). (а) (б) Рис. 7.3 Все приведённые ранее примеры Л^Р-задач (задачи 1-12 из 4-го параграфа) являются ТУР-ПОЛНЫМИ задачами. Список iVP-полных задач в настоящее время 229