Пример

Чтобы лучше понять суть того, что происходит в доказательстве (8.13), мы рас- смотрим простой и конкретный пример. Допустим, имеется следующая задача.

Содержит ли заданный граф G независимое множество из двух узлов?

Обратите внимание: эта задача принадлежит к категории NP.

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

Следуя структуре приведенного выше доказательства, мы сначала рассмотрим эффективный сертифицирующий алгоритм для этой задачи. Входные данные s

представляют граф из n узлов, который будет задаваться

пары узлов будет присутствовать бит, указывающий, соединены ли эти два узла ребром. Сертификат t может задаваться n битами: для каждого узла включается бит, указывающий, принадлежит ли этот узел предлагаемому независимому мно- жеству. Эффективный сертифицирующий алгоритм должен проверить два факта: что по крайней мере два бита в t равны 1 и что никакие два бита в t не равны 1, если они представляют два конца ребра (что определяется соответствующим битом в 5).

Теперь для конкретной длины n, соответствующей интересующим нас входным данным s, строится эквивалентная схема K. Предположим, к примеру, что мы хотим получить ответ на задачу для графа G с тремя узлами u, v, w, в котором узел v со- единен с и и w. Это означает, что мы имеем дело с вводом длины n = 3. На рис. 8.5 изображена схема, эквивалентная эффективному сертифицирующему алгоритму для нашей задачи с произвольным графом из трех узлов. (Фактически правая часть схемы проверяет, что были выбраны как минимум два узла, а левая — что не были выбраны оба конца любого ребра). Ребра G кодируются константами в первых трех источниках, а остальные три источника (представляющие узлы, включаемые в не- зависимое множество) остаются переменными. Заметим, что выполнимость этого экземпляра задачи выполнимости схемы проверяется передачей 1, 0, 1 на вход. Это соответствует выбору узлов и и w, которые действительно образуют независимое множество из двух узлов в трехузловом графе G.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Пример:

  1. Примеры жестокости по отношению к другим (эти примеры более всего относятся к семейной жизни):
  2. ПРИМЕР 2
  3. Пример 1.
  4. ПРИМЕР 2
  5. Пример 2.
  6. Пример 2.
  7. Пример 2.
  8. Пример.
  9. ПРИМЕР
  10. Действенность примеров
  11. ПРИМЕР 2
  12. Пример 4.
  13. Заключение по примерам
  14. Пример «чуда».