34. Что такое оценка сложности задачи?

Минимум сложности алгоритма, взятый по множеству всех алгоритмов, решающих эту задачу

35. Какая именно сложность рассматривается при изучении теории вычислительной сложности?

Понятие временной сложности (трудоемкости) алгоритмов, т.е. построение выражений T(n) = O(f(n)), характеризующих время работы данного алгоритма при больших N.

36. Что такое массовая задача и индивидуальная задача?

Массовая задача - это класс однотипных задач, различающихся значениями исходных данных. Например, массовыми являются: задача решения квадратного уравнения (с произвольными коэффициентами), задача раскраски графа (любого заданного). Обозначение z Î Z означает, что индивидуальная задача z принадлежит классу задач Z (например, Z - задача решения квадратного уравнения, а z - задача решения уравнения 2x² + 5x - 3 = 0).

37. Что является аргументом функций, оценивающих сложность алгоритмов и задач?

«длина описания задачи», под которой понимается количество битов информации, необходимое, чтобы выделить из массовой задачи конкретную индивидуальную задачу. Например, для многих задач теории графов описанием задачи может быть матрица смежности конкретного графа или другая форма задания графа.

Для задачи решения квадратного уравнения описание задачи – это три коэффициента уравнения, а длина описания зависит от возможного диапазона значений этих коэффициентов. Если используются двухбайтовые целые коэффициенты, то длина описания равна 6 байтам или 48 битам

38. Почему машина Тьюринга используется как основная вычислительная модель в теории сложности вычислений?

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

39. Что такое полиномиальный алгоритм?

Алгоритм, имеющий оценку сложности O(n^k) для некоторого k.

40. Что такое задача распознавания?

Такие задачи, где требуется ответ «Да / Нет». Например, «Имеется ли маршрут коммивояжера короче 1000 км?»

41. Что такое класс задач P?

P - класс полиномиальных задач. С ростом длины описания задачи время растёт полиномиальной.

В теории алгоритмов классом P (от англ. polynomial) называют множество алгоритмов, время работы которых не слишком сильно зависит от размера входных данных (не превосходит многочлена от размера данных). Алгоритмы, принадлежащие классу P, считаются быстрыми.

42. Что такое полиномиальная сводимость задач?

Пусть даны две массовые задачи распознавания Z и Z'. Задача Z полиномиально сводима к задаче Z' (обозначается Z * Z'), если существует алгоритм A, который переводит описание любой индивидуальной задачи z * Z в описание индивидуальной задачи z' * Z', и при этом:

1) эти индивидуальные задачи эквивалентны (либо обе имеют ответ «Да», либо обе «Нет»)

2) время работы алгоритма A ограничено некоторым полиномом P(l), где l – длина описания задачи z; очевидно, что той же величиной P(l) будет ограничена и длина описания задачи z'.

43. Как связана принадлежность задач к классу P с их полиномиальной сводимостью?

Если для двух массовых задач Z и Z' имеет место полиномиальная сводимость Z * Z', то можно утверждать следующее:

1) если задача Z' полиномиальна, то и Z тоже полиномиальна (или короче:

Z' * P * Z * P);

2) если Z не является полиномиальной, то и Z' тоже не является

(Z * ~P  Z' * ~P).

44. Что такое недетерминированная машина Тьюринга (НМТ)?

Недетерминированная машина Тьюринга (НМТ) - МТ в которой возможны несколько правил перехода с одинаковой левой частью и различными правыми частями. Вот машина на очередном такте пришла в состояние, которому соответствуют несколько разных правил перехода. По определению НМТ, в этом случае допустимым считается любой выбор правила.

45. В чем принципиальность отличия НМТ от детерминированной МТ?

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

Также у НМТ присутствует разветвленность.

46. Как можно представить себе работу НМТ?

(деревом)

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

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

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

через конечное число тактов МТ достигает состояния qy. При этом неважно, как ведут себя другие ветви: там может быть и состояние q_n, и бесконечные ветви.

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

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

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

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

полиномиально проверяемые задачи (ПП-задачи). Это вот что такое. Пусть каким-то образом получен план X (с неба, например, свалился). Если детерминированная МТ может за время не более P(l) проверить, является ли этот план допустимым, то данная задача является ПП-задачей.

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

P вложено в NP

Все полиномиальные задачи P Í NP, поскольку детерминированная МТ – частный случай недетерминированной.

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

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

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

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

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

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

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

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

Z0- универс.NP задача(закод в НМТ)Выберем алгор., который сводит Z0 к индивид Z1

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

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