Примеры массовых задач

Пример 1. Изоморфизм подграфу

Условие:

Даны 2 графа G₁ = (V₁,E₁) и G₂ = (V₂,E₂).

Верно ли, что G₁ содержит подграф, изоморфный G₂? Другими словами, существуют ли:

1) Подмножества ,такие, что ,.

2) Взаимнооднозначная функция f, отображающая , такая, что ребро существует тогда и только тогда, когда существует ребро ?

ПРИМЕР 2. КОММИВОЯЖЕР

Условие:

Заданы конечное множество городов C={C₁, C₂, … , C_n}, расстоянияd(C_i, C_j) и граница B, являющаяся натуральным числом.

Существует ли замкнутый маршрут, проходящий через все города из C по одному разу, длина которого не превосходит B, т.е. существует ли последовательность <C_р(1), C_р(2),…, C_р(n)> такая, что?

Подобным образом строится соответствие между любой оптимизационной задачей и задачей распознавания свойств. Здесь важно отметить, что поскольку значение функции легко оценить, то задача распознавания не будет сложнее, чем оптимизационные задачи. Если задача распознавания может быть решена за полиномиальное время, то, решая её некоторое количество раз (ограниченное полиномом от размерности задачи) при различных значениях параметра B, мы сможем решить и оптимизационную задачу.

Теория NP – полных задач ограничивается только задачами распознавания. Это объясняется тем, что задача распознавания имеет естественный формальный эквивалент, удобный для изучения методами теории вычислений. Этот эквивалент называется языком и определяется следующим образом. Для любого конечного множества символов , называемого алфавитом, и– множества всех конечных цепочек, любое подмножествоназывается языком в алфавите. Соответствие между языком и задачами распознавания устанавливается с помощью схем кодирования. Схема кодирования e задачи П описывает каждую индивидуальную задачу из П подходящим словом в некотором фиксированном алфавите. Таким образом, задача П, схема кодирования e задачи П разбивают слова изна три класса:

1) Слова не являются кодами индивидуальной задачи из П.

2) Слова являются кодами индивидуальной задачи из П с отрицательным ответом на вопрос.

3) Слова являются кодами индивидуальной задачи из П с положительным ответом на вопрос.

Третий класс слов является тем языком, который ставится в соответствие задаче П при схеме кодирования е и обозначается ={: x - код индивидуальной задачи I из множества YП со схемой кодирования e}.

При применении формальной теории NP – полноты к задачам распознавания, будем говорить, что некоторый результат имеет место для задачи П при схеме кодирования e, если результат имеет место для языка . Если е и е’ – любые две разумные схемы кодирования для задачи П, то рассматриваемое свойство языковивыполняется или не выполняется одновременно, это позволяет не указывать явно схемы кодирования, т.е. мы можем неформально говорить, что рассматриваемое свойство для задачи П выполняется или не выполняется.

Будем считать, что с каждой задачей распознавания связана независящая от схемы кодирования функция Length, которая отображает DПN – это функция полиномиально эквивалентна длине кода индивидуальной задачи, полученной при любой разумной кодировке. Полиномиальная эквивалентность понимается в следующем смысле: для любой разумной схемы кодирования e задачи П существуют два полинома p и p’ такие, что для любой индивидуальной задачи I из DП, если x – длина её кода, то Length(I)<p(x) и x<p’(Length(I)).

Например, в задаче ИЗОМОРФИЗМ ПОДГРАФУ можно положить Length(I)=|V₁|+|V₂|, где G₁=(V₁,E₁) и G₂=(V₂,E₂) – графы, образующие индивидуальные задачи.

В задаче О КОММИВОЯЖЁРЕ можно определить функцию

Length(I)=n++max(log d(C_i, C_j) :).

Здесь bпонимается как наименьшее целое число, большее или равное аргументу b.

Обычно схему кодирования считают разумной, если она достаточно сжата и допускает декодирование. Сжимать нужно для того, чтобы при кодировании индивидуальной задачи сохранялась её естественная краткость, когда её решают на компьютере, и не допускалось искусственное раздувание входа.

Смысл понятия декодируемость заключается в том, чтобы по данной компоненте условия задачи можно было бы указать алгоритм с полиномиальным временем работы, который из любого заданного кода индивидуальной задачи позволял бы извлечь описание этой компоненты.