Вопрос: понятие р и np – задач:

Полиномиальный алгоритм – это алгоритм с полиномиальной трудоемкостью (временем работы). Полиномиальный или экспоненциальный характер работы алгоритма инвариантен относительно формы представления входных данных (двоичная, десятичная или другая система счисления). Говорят, что алгоритм является полиномиальным, если время его работы, т. е. временная сложность, ограничивается сверху полиномом некоторой степени T(N)=O(N^m). Тогда все задачи, которые решаются таким алгоритмом, образуют Р-класс задач. Задачи, временная сложность которых экспоненциальна (T(N)=O(K^N)), не входят в Р.

В недетерминированном алгоритме (НДА) для любого данного состояния может быть больше одного допустимого следующего состояния, т. е. такой алгоритм в каждый момент времени может выполнить больше одного оператора. НДА не является случайным или вероятностным алгоритмом. Он представляет собой алгоритм, который может находиться во многих состояниях (это эквивалентно параллельному решению задачи с множеством вариантов). Детерминированный алгоритм (ДА) решал бы эту задачу последовательно (перебор всех вариантов, сравнение с критерием оптимальности K₀ до тех пор, пока не выберет альтернативу А₀). НДА может одновременно (параллельно) получить все альтернативы и сравнить с K₀, копируя самого себя в виде отдельного процесса для каждой альтернативы, которая выполняется независимо. При этом если какая-либо копия обнаружит, что получен неправильный результат или результат не получен, то она прекращает свое исполнение. Если же копия находит решение, удовлетворяющее K₀, то она объявляет об успехе, и все другие копии прекращают работу.

НДА характеризуется тремя параметрами:

выбор – многозначная функция, значения которой являются элементами множества S;

неудача заставляет копию алгоритма прекратить работу;

успех заставляет все копии алгоритма прекратить работу и сформировать результат.

Очевидно, что никакое физическое устройство не способно на неограниченное недетерминированное поведение, значит, НДА является теоретическим методом. Задачи, которые можно решить с помощью полиномиального НДА, образуют класс NP-задач.

Вопрос: np – трудные и np – полные задачи:

Задача, входящая в Р, является NP-трудной, если существует полиномиальный ДА (ПДА) ее решения, который модно использовать для получения решения всех задач, входящих в NP. Т. е. такая задача является NP-трудной, если она, по крайней мере, так же трудна, как любая задача, входящая в NP.

NP-трудная задача, принадлежащая NP, называется NP-полной задачей. Такие задачи не менее трудны, чем любая задача из NP. При этом существование ПДА для NP-трудной или NP-полной задачи означает, что классы Р и NP совпадают, т. е. возможно решение всех задач 3-го класса быстрым алгоритмом.

Для доказательства того, что задача является NP-трудной, необходимо показать, что если для задачи существует ПДА, то его можно использовать для получения другого ПДА решения задач, входящих в NP. Чтобы установить, что задача является NP-полной, необходимо доказать, что она принадлежит NP. Идея использовать алгоритм решения одной задачи для получения алгоритма решения другой является одной из наиболее важных в теории алгоритмов.

Определение 1: Задача Р1 преобразуется в задачу Р2, если любой частный случай задачи Р1 можно преобразовать за полиномиальное время в некоторый частный случай задачи Р2. Тогда решение Р1 можно получить за полиномиальное время из решения частного случая задачи Р2.

Определение 2: Задача является NP-трудной, если каждая задача, входящая в NP, преобразуется в нее. Задача является NP-полной, если она является одновременно NP-трудной и принадлежит NP.

Вопрос: алгоритмически неразрешимые проблемы:

Разделяют проблемы одиночные и массовые.

Принципиально неразрешимыми должны быть алгоритмы получения объектов, которые парадоксальны, или решения задач, из которых вытекало бы существование парадоксальных объектов.

Например, парадоксами являются:

1) 5-ая аксиома Евклида (Лобачевский дал ей опровержение).

2) 2*2=5

Пример 1:

Теорема Ферма:

Не существует таких целых чисел a, b, с, n (n>2), для которых справедливо равенство

aⁿ + bⁿ = cⁿ

Эта теорема была доказана для многих значений n и проверена для частных случаев, однако до сих пор не создано общее доказательство теоремы.

Вопрос: примеры задач NP – класса:

Пусть х₁, х₂, …, х_n – множество логических переменных; – их отрицания или дополнения.

if x_i = true then = false

 - И;  - ИЛИ.

Дизъюнкция: х₁  х₅  …

Конъюнкция: х₄  х₃  …

Конъюнктивная нормальная форма:

E^*(x₁, …, x_n) = (x₁  x₂  x₃)  (x₁   )  (  x₄)  ( ) (*)

Задача о выполнимости заключается в определении, является ли булевская функция, записанная в КНФ, выполнимой. Любая булевская функция может быть представлена в КНФ по правилу Де Моргана:

А(ВС)=( АВ)(АС)

Говорят, что булевская функция выполнима, если существует некоторое присваивание переменным true или false, при этом функция должна быть равна true.

Для функции (*) она будет выполнима, если ввести следующие присваивания:

(*)