Задач распознавания свойств (зрс)

• Основные понятия теории NP-полноты

• PNP?

• Задачи распознавания свойств

• Класс задач распознавания свойств (ЗРС) – множество проблем, решением которых является ответ «Да» или «Нет».
• ГАМИЛЬТОНОВ ЦИКЛ (ГЦ).
• Задан граф G = (V, E).
• Спрашивается, содержит ли G гамильтонов цикл?
• Opt задаче max{f(x) : x  D} соответствует ЗРС:
• « ли решение x  D: f(x)  Q?», где Q – заданное число.
• КОММИВОЯЖЕР (КМ). Дано:
• N – список городов;
• cij – расстояния между городами i,j  N; B  R.
•  ли гамильтонов контур, длина которого  B?

• Задачи

• Под общей (массовой) задачей (проблемой) P понимается некоторый общий вопрос, требующий ответа.
• Общая задача, как правило, содержит некоторые параметры. В задаче КМ, например, это расстояния между городами.
• Если все параметры общей задачи принимают конкретные значения, то такую задачу называют индивидуальной.

• Трудоёмкость алгоритма

• Количество символов в стандартном (двоичном)
• представлении данных инд. задачи XP наз. длиной входа
• и обозначим L(X).

• наз. трудоемкостью алг. A.

• , где d – целое положительное число

• Алг., трудоемкость которого не ограничена полиномом от длины входа, наз. экспоненциальным.

• Пусть алг. A решает проблему P и tA(X) количество элементарных операций, выполняемых алгоритмом A при решении инд. задачи XP. Тогда функция

• Алг. A наз.