Примеры. Массовая задача и изоморфизм подграфу.

ПРИМЕР 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, мы сможем решить и оптимизационную задачу.

12. Язык. Связь между задачами распознавания и языками. Задачи разновидности языка и кодирование.

Из соображения удобства теория NP – полных задач строится только для задач распознавания свойств. Такие задачи имеют только два возможных решения: “да” и “нет”. Формально, задачи распознавания П состоят из двух множеств: 1) множество D_П всех возможных индивидуальных задач; 2) Множество индивидуальных задач с ответом “да”. Стандартная форма, которую мы будем применять для описания задач, состоит из двух частей: в первой части даётся описание условия задачи в терминах различных компонентов, во второй части формулируется вопрос-предположение, предполагающий один из двух ответов “да” или “нет”. Это описание определяет множествоD_П и Y_П. Индивидуальная задача принадлежит множеству D_П в том случае, когда она может быть получена из стандартной формы описания подстановкой конкретных значений во все компоненты условий индивидуальных задач, множеству Y_П в том случае, когда ответом на вопрос задачи будет “да”.

Примеры. Массовая задача и изоморфизм подграфу.

ПРИМЕР 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 понимается как наименьшее целое число, большее или равное аргументу.

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

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