Задачи разновидности языка и кодирование.

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

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

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