Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Смысл сводимости

Читайте также:
  1. Gt;§ 2. Действия, производимые изменением количества денег (M). Количественная теория в причинном смысле
  2. II Философская концепция Э.Фромма: основные позиции, критика и переосмысление источников, открытия.
  3. II. Соотношение — вначале самопроизвольное, затем систематическое — между положительным мышлением и всеобщим здравым смыслом
  4. III. Стадия осмысления
  5. Адекватно расшифровать эмоциональный, сигнал партнера означает уловить в нем именно тот смысл, который в него был вложен.
  6. Биологический смысл онкотического давление.
  7. В некотором смысле, «свобода» в Революции – сама Революция, непрерывная и безудержная вакханалия блуда, гордости, злобы и обиды.

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

Если для некоторой задачи Z построен алгоритм сложности O(f(n)), то можно говорить, что сложность решения задачи не превосходит O(f(n)). Таким образом, верхние оценки сложности решения задачи могут быть получены конструктивным образом с помощью построения конкретных алгоритмов. Нижние оценки - это утверждения следующего типа: "Задача Z не может быть решена никаким алгоритмом со сложностью, меньшей O(g(n))". Эти оценки нельзя получить, построив конкретный алгоритм. (Может быть, это просто плохой алгоритм, а в будущем кто-то построит хороший.) Эти оценки строятся путем анализа свойств задачи, возможностей кодировок условия и пр. Тривиальная нижняя оценка - длина входа задачи. Но выше мы видели, что проблемы кодировки входа достаточно тонкие. Хотя в большинстве случаев здесь можно все прояснить.

Лишь для небольшого количества задач верхние и нижние оценки сложности близки. Например, сложность сортировки n чисел равна O(nlogn). То есть, известен конкретный алгоритм, который с такой сложностью сортирует n чисел. Кроме того, доказано, что эту задачу нельзя решить быстрее, чем за O(nlogn) шагов.

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

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

Вот для этого и служит понятие сводимости. Это, грубо говоря, установление некоторой связи между парой задач. Смысл этой связи иллюстрирует следующий пример. Пусть известно две задачи X и Y. Задача X сформулирована 200 лет назад и с тех пор ничего лучшего, чем экспоненциальный алгоритм для нее не построено. Задача Y сформулирована вчера, и мы хотим приложить максимум усилий для ее эффективного решения. Под таким решением мы подразумеваем полиномиальный алгоритм.

Предположим теперь, что существует некоторое понятие сводимости. Если эта сводимость так устанавливается между X и Y, что наличие полиномиального алгоритма для Y влечет за собой существование полиномиального алгоритма для X, то интуитивно ясно, что подобный факт существенно повлияет на наш оптимизм в вопросе эффективного решения задачи Y и, возможно, после здравого рассуждения мы ограничимся эвристиками и переборными алгоритмами для нашей новой задачи.

Было введено несколько определений сводимости.


Дата добавления: 2015-07-11; просмотров: 95 | Нарушение авторских прав


Читайте в этой же книге: Нормальные алгорифмы Маркова (НАМ). | Одноленточная МТ | Недетерминированная МТ | Оракульная МТ | Равнодоступная адресная машина (РАМ) и некоторые другие подходы. | Кодировки входных данных. | О мерах сложности | Теоремы сравнения | Задача о кратчайшем (минимальном) остове (остовном дереве). | Схемы из функциональных элементов |
<== предыдущая страница | следующая страница ==>
Классы P и NP.| Полиномиальная сводимость

mybiblioteka.su - 2015-2019 год. (0.006 сек.)