44. Что означает выражение «задача z принимается данной нмт»?

Любая конкретная НМТ, как и детерминированная МТ, решает некоторую массовую задачу распознавания Z, при этом в начальном состоянии лента содержит описание индивидуальной задачи z * Z. Будем говорить, что индивидуальная задача принимается данной детерминированной МТ, если через конечное число тактов МТ достигает состояния qy. Наоборот, задача не принимается, если МТ приходит в состояние qn или вообще не останавливается (обратите внимание на асимметрию этих определений).

Аналогичным образом, будем говорить, что НМТ принимает индивидуальную задачу распознавания, если существует такое допустимое вычисление (т.е. существует ветвь дерева), которое завершается состоянием qy. При этом неважно, как ведут себя другие ветви: там может быть и состояние qn, и бесконечные ветви.

НМТ не принимает задачу, если любая ветвь вычислений либо бесконечна, либо заканчивается состоянием qn.

45. Что такое класс задач NP?

Говорят, что массовая задача распознавания принадлежит классу недетерминированно полиномиальных задач (Z  NP), если существует такая НМТ, решающая эту задачу, время работы которой для всех принимаемых индивидуальных задач не превышает некоторого полинома P(l), где l = |z|.

46. Что такое полиномиально проверяемые задачи?

Что за задачи принадлежат классу NP? Их огромное количество. Во-первых, к ним относятся все полиномиальные задачи (P * NP. поскольку детерминированная МТ – частный случай недетерминированной). Во-вторых, к классу NP относятся все полиномиально проверяемые задачи (ПП-задачи). Это вот что такое. Пусть каким-то образом получен план X (с неба, например, свалился). Если детерминированная МТ может за время не более P(l) проверить, является ли этот план допустимым, то данная задача является ПП-задачей. Нетрудно показать, что все ПП-задачи принадлежат NP.

47. Как соотносятся классы задач P и NP?

Как было сказано выше, P включается в NP. В настоящее время для множества задач из NP неизвестен полиномиальный алгоритм решения, однако не найдено ни одной NP-задачи, для которой было бы доказано, что полиномиальный алгоритм невозможен. Таким образом, остается открытым вопрос, имеет ли место равенство P = NP. Не исключено, что этот вопрос будет висеть вечно.

48. Относится ли задача сортировки массива к классу P? к классу NP?

Не относится. Почему это не относится?! сложность у нее - вполне себе полиномиальная. даже мы делали такое на машине тьюринга на лабе у балабаевой. и к НП тоже относится, потому что П включается в НП.

49. Что такое NP-трудная задача?

Задача Z называется NP-трудной, если любая другая задача Z', принадлежащая  NP полиномиально сводима к задаче Z

50. Что такое NP-полная задача?

Задача Z называется NP-полной, если Z есть NP-трудная задача и Z * NP.

51. Может ли полиномиальный алгоритм решать NP-полную задачу?

Получается, что NP-полные задачи – как бы самые сложные задачи в классе NP: если для одной (любой) из этих задач будет найден полиномиальный алгоритм решения, то тогда любую NP-задачу можно будет решить за полиномиальное время. Для этого ее следует свести к соответствующей NP-полной задаче (за полиномиальное время!) и решить NP-полную задачу (тоже за полиномиальное время). Иначе говоря, если одна какая-нибудь NP-полная задача принадлежит классу P, то тогда классы P и NP полностью совпадают. Таким образом, отыскание хотя бы одного полиномиального алгоритма для какой-нибудь NP-полной задачи стало бы эпохальным событием в истории информатики.

52. Нарисуйте соотношение между множествами NP-трудных задач, NP-полных задач, множеством NP и множеством P.

P включается в NP, NP-трудные пересекаются с NP и P. NP полные - то кусок, где NP-трудные пересекаются с NP и не пересекаются c P.

53. В чем идея теоремы Кука?

доказательство NP-полноты одной конкретной задачи.

Как вообще можно доказать сводимость всех NP-задач к данной задаче? Можно воспользоваться определением NP-задачи: для нее имеется НМТ, принимающая индивидуальные задачи за полиномиальное время. А каждую НМТ можно описать, закодировав ее правила перехода. Тогда любую NP-задачу можно сформулировать следующим образом. Дано описание НМТ для данной массовой задачи Z и дано описание индивидуальной задачи z * Z в виде записи с длиной l на ленте этой НМТ. Верно ли, что существует допустимое вычисление этой НМТ при этом исходном состоянии ленты, которое не более, чем за P(l) тактов приводит в состояние qy? Заметьте, что специфика конкретной задачи Z здесь исчезла, или вернее – она закодирована в правилах НМТ. Назовем такую «универсальную» NP-задачу Z0.

Теперь нам нужно сделать следующее. Нужно выбрать некоторую задачу распознавания Z1 и предложить алгоритм, который за полиномиальное (относительно l) время будет переводить описание индивидуальной задачи z0 * Z0 в описание эквивалентной индивидуальной задачи z1 * Z1. Тогда ясно, что задача Z1 является NP-трудной, поскольку мы фактически умеем полиномиально сводить к ней любую NP-задачу.

54. Сформулируйте теорему Кука.

Рассмотрим задачу о выполнимости КНФ.

Даны переменные X = {xi, i=1...N} и конъюнктивная нормальная форма (КНФ) G(X). Существует ли такой план X, для которого G(X) = 1?

Теорема Кука. Задача о выполнимости КНФ NP-полна.

55. Как формулируется задача о выполнимости КНФ?

Рассмотрим задачу о выполнимости КНФ.

Даны переменные X = {xi, i=1...N} и конъюнктивная нормальная форма (КНФ) G(X). Существует ли такой план X, для которого G(X) = 1?

56. Каков смысл каждого из 6 типов условий, накладываемых на НМТ в доказательстве теоремы Кука?

Чтобы выделить допустимые вычисления НМТ, следует наложить еще некоторые условия на значения переменных. Таковые условия можно объединить в 6 групп. Опишем их сначала словесно.

1. На любом такте работы НМТ находится ровно в одном состоянии.

2. На любом такте работы головка НМТ находится ровно в одной позиции ленты.

3. На любом такте работы каждая ячейка ленты содержит ровно одну букву ленточного алфавита.

4. На такте i = 0 НМТ находится в состоянии q0, головка на ячейке 1, на ленте записано описание решаемой индивидуальной задачи.

5. Не позднее, чем через P(l) тактов НМТ приходит в состояние qy (принимает задачу).

6. Все изменения конфигурации НМТ между тактами i и i+1 происходят в соответствии с правилами перехода данной НМТ.

57. Каков смысл этих условий в совокупности?

Чтобы выделить допустимые вычисления НМТ Такое подробное изложение довольно очевидных вещей нужно для того, чтобы от словесных условий перейти к формально заданным.

Для формализации условий корректности вполне подходит аппарат КНФ.

58. Какую практическую пользу может принести доказательство NP-полноты конкретной задачи?

Пусть имеется одна доказанно NP-полная задача Z1. Чтобы доказать NP-полноту задачи Z₂, достаточно сделать две вещи: во-первых, показать, что Z₂ Î NP (это обычно несложно), и во-вторых, суметь построить полиномиальное сведение Z₁ µ Z₂ (а не Z₂ µ Z₁, обратите внимание на направление!) Тогда получается, что любая NP-задача Z полиномиально сводится к Z₂ через Z₁. Теперь у нас есть уже две NP-полные задачи, Z₁ и Z₂, и для следующей задачи Z₃ можно уже выбирать, что легче доказать: Z₁ µ Z₃ или Z₂ µ Z₃. И так далее. В настоящее время известны сотни (если уже не тысячи) NP-полных и NP-трудных задач.

Поскольку Z – произвольная задача из NP, то доказана полиномиальная сводимость любой NP-задачи к задаче ВЫП. В то же время задача ВЫП, очевидно, проверяема за полиномиальное время (на самом деле даже за линейное: для проверки нужно просто подставить значения переменных в КНФ и убедиться, что все элементарные дизъюнкции истинны), а потому эта задача принадлежит NP. Значит, задача ВЫП является NP-полной, что и требовалось доказать.

59. Как доказывается NP-полнота конкретных задач?

Их полиномиально сводят к задачам NP-полнота которых уже доказана.

60. Сформулируйте задачу «3-выполнимость».

дана КНФ от переменных x1, x2, ... xn, но при этом каждая элементарная дизъюнкция содержит ровно три члена. Требуется определить, существует ли набор значений переменных, при котором КНФ равна 1.

61. В чем идея доказательства NP-полноты задачи «3-выполнимость»?

Очевидно, что данная задача принадлежит NP, т.к. она представляет собой частный случай задачи ВЫП. Чтобы доказать NP-полноту, следует показать, что задачу ВЫП можно полиномиально свести к 3-ВЫП.

62. Сформулируйте задачу о вершинном покрытии графа.

Дан неориентированный граф G = (V, E) с множеством вершин V и множеством ребер E. Дано натуральное число K. Вершинным покрытием графа называется подмножество вершин V* * V, такое, что любое ребро графа инцидентно хотя бы одной вершине из V*. Требуется определить, существует ли вершинное покрытие графа G мощности * K.

63. В чем идея доказательства NP-полноты задачи о вершинном покрытии?

Для доказательства NP-полноты задачи ВП покажем, что к ней сводится задача 3 ВЫП. Как и раньше, вместо строгого доказательства покажем основные идеи на примере.

64. Из каких частей состоит граф, строящийся в этом доказательстве?

Пусть дана следующая КНФ: (x1 **x3 **x4) & (*x1 * x2 **x4). Число переменных n=4, число дизъюнкций m=2. Построим граф G по следующим правилам:

1. Для каждой переменной xi построим подграф из двух вершин, соединенных ребром. Пометим вершины символами xi и*xi.

2. Для каждой дизъюнкции ak построим подграф-треугольник, пометив его вершины символами ak1, ak2 и ak3.

3. Соединим каждую вершину каждого треугольника с вершиной, помеченной соответствующей переменной. Например, поскольку вторым символом первой дизъюнкции является *x3, следует соединить ребром вершины a12 и *x3. Эту группу ребер будем называть соединяющими ребрами.

Результат построения показан на рис.2.1.

Рис.2.1

Выберем значение K = n+2m = 8.

Докажем теперь, что в построенном графе G имеется вершинное покрытие V* мощности не более K в том и только том случае, если для исходной КНФ имеется выполняющий набор значений переменных.

Рассмотрим сначала, как может выглядеть вершинное покрытие для данного графа. Очевидно, в него должна входить по меньшей мере одна вершина из каждого подграфа xi -*xi, чтобы покрыть ребро этого подграфа. Из каждого треугольного подграфа ak в покрытие должны войти по крайней мере две вершины. Итого получается не менее n+2m = K вершин. Но при этом по условию задачи ВП покрытие должно содержать не более K вершин. Таким образом, покрытие должно содержать ровно K вершин, по одной из каждого подграфа xi -*xi и по две из подграфов ak .

Предположим, такое покрытие существует. При этом должны быть покрыты также все соединяющие ребра. Для каждого ak два таких ребра покрыты двумя вершинами ak, вошедшими в покрытие. Третье же соединяющее ребро должно быть покрыто вершиной из пары xi -*xi. Выпишем набор значений всех xi, соответствующий вершинам, вошедшим в покрытие. По построению графа очевидно, что при этих значениях переменных в каждую дизъюнкцию будет входить, по крайней мере, один истинный символ, т.е. КНФ будет выполнена.

Наоборот, пусть существует набор значений xi, обращающий в истину все дизъюнкции из КНФ. Включим в покрытие n вершин, помеченных символами этого набора. При этом, поскольку в каждой дизъюнкции присутствует хотя бы один символ из выполняющего набора, для каждого подграфа ak будет покрыто хотя бы одно соединяющее ребро. Включим в покрытие те две вершины ak, которые неинцидентны этому ребру (не лежат на нем). Выполним это для всех ak. При этом окажутся покрыты оставшиеся соединяющие ребра и все ребра подграфов ak, т.е. будет полностью построено вершинное покрытие из K вершин.

Эквивалентность задачи ВП и задачи 3-ВЫП доказана. Полиномиальность сведения не вызывает сомнений. Полиномиальная проверяемость задачи ВП тоже очевидна. Значит, задача ВП является NP-полной.