misle.ru страница 1
скачать файл

Минимальная эквивалентная ДНФ (МинЭквДНФ)

Результаты


  1. Постановка задачи

    1. В форме зачадчи минимизации

    2. В форма задачи распознавания

  2. Доказательство приналдлежности задачи классу NPNP

  3. Полнота в классе NPNP

  4. Доказательство несуществования полиномиального алгоритма, решающего задачу МинЭквДНФ с точностью до аддитивной константы

  5. Доказательство несуществования полиномиального алгоритма, решающего задачу МинЭквДНФ с точностью до мультипликативной константы

  6. Частные случаи

    1. Для 1-ДНФ существует линейный алгоритм построения МинЭквДНФ

    2. Для 2-ДНФ – ?

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



Постановка задачи


Определение: размером ДНФ D(x­1, x2, …, xN) назовем суммарное количесво вхождений всех переменных. Обозначим как |D(x­1, x2, …, xN)|.

Определение: минимальной эквивалентной ДНФ для данной ДНФ D(x­1, x2, …, xN) назовем такую ДНФ F(x­1, x2, …, xN), что:



  1. F ≡ D

  2.  F’ ≡ D |F|  |F’|

Постановка задачи в форме задачи минимизации


Задано множество переменных U = {­x1, x2, …, xN} и ДНФ D над переменными U. Требуется найти минимальную ДНФ, эквивалентную D.

Постановка задачи в форме задачи распознавания


Задано множество переменных U = {­x1, x2, …, xN}, ДНФ D над переменными U и целое положительное число k. Требуется определить, существует ли ДНФ F над пременными U, такая что:

  1. F ≡ D

  2. |F|  k

Принадлежность задачи МинЭквДНФ классу NPNP


Теорма 1: задача МинЭквДНФ принадлежит классу NPNP

Доказательство: покажем, что имеет место недетерминированная полиномиальная сводимость по Тьюрингу задачи МинЭквДНФ (в форме задачи распознавания) к задаче ВЫП.

Пусть имеется гипотетическая процедура ВЫП(), которая отвечает на вопрос «выполнима ли функция », где  -- булева фукция. Построим недетерминированный алгоритм решения задачи МинЭквДНФ. На стадии угадывания формируем ДНФ G, такую что |G|  k. Для проверки произведем вызов ВЫП(­­­ (D ≡ G)). Если окажется, что фукция  = (D ≡ G) невыполнима, то G будет искомой ДНФ.

Покажем, что сводимость действительно полиномиальная. Во-первых, длина догадки не превосходит длины исходной ДНФ (Если |G|  k, ответом на исходную задачу будет «да»), а значит она ограничена полиномом. Во-вторых, на стадии проверки мы произвели один вызов гипотетической процедуры ВЫП, а значит, если ВЫП будет полиномиальной, то и построенный алгоритм будет полиномиальным.


Полнота в классе NPNP


Полнота задачи МинЭквДНФ показана в статье “The Minimum Equivalent DNF Problem and Shortest Implicants”, Christopher Umans, Computer Science Division, University of California, Berkley. Статья приведена в приложении А.

Несуществование полиномиального алгоритма, решающего задачу МинЭквДНФ с точностью до аддитивной константы


Определение: длину минимальной эквивалентной ДНФ для заданой ДНФ D обозначим как OPT(D)

Лемма 1: существует полиномиальный алгоритм для проверки выполнимости ДНФ

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

Лемма 2: пусть дана некоторая ДНФ D(­x1, x2, …, xN), целое положительное число k, алгоритм A, принимающий на вход произвольную ДНФ D и возвращающий ДНФ, такой что:



  1. D ≡ A(D)

  2. |A(D)|  OPT(D) + k

Положим G = D(­x11, x21, …, xN1)  D(­x12, x22, …, xN2)  …  D(­x1 k+1, x2 k+1, …, xNk+1)

Тогда: |A(G)|  k  (D ≡ true)  (D ≡ false)

Доказательство:

: пусть (D ≡ true)  (D ≡ false). В таком случае OPT(D) = OPT(G) = 0, а значит |A(G)|  OPT(G) + k = k.

: пусть |A(G)|  k. В таком случае,  i: ДНФ A(G) не содержит переменных xji, то есть не зависит от переменных {­x1i, x2i, …, xNi}. Это возможно только когда D ≡ true либо D ≡ false.

Теорема 1: В предположении, что P ≠ NP, не существует полиномиального алгоритма A, решающего задачу МинЭквДНФ, такого что  ДНФ D |A(D)|  OPT(D) + k, где k – фиксированное целое положительное число.

Доказательство: доказательство проведем от противного. Предположим, что существует некоторый полиномиальный алгоритм A и целое положительное число k, такие что  ДНФ D |A(D)|  OPT(D) + k. Построим полиномиальный алгоритм для решения задачи ВЫП.

Пусть дан экземляр задачи ВЫП: дана КНФ F(x1, x2, ..., x­­­­N), требуется выяснить, существует ли такой набор {σ­1, σ­2, ..., σ­N}, что F(σ­1, σ­2, ..., σ­N) = true. Построим ДНФ D = F. Данное построение делается за линейное время, с помощью правил (a & b) = a  b и (a  b) = a & b. F выполнима  (F ≡ false)  (D ≡ true). Утверждение (D ≡ false) можно проверить за полиномиальное время (по лемме 1).

По ДНФ D построим новую ДНФ G от N * (k + 1) переменных таким образом:

G = D(x11, x21, ..., x­­­­N1)  D(x12, x22, ..., x­­­­N2)  ...  D(x1k+1, x2k+1, ..., x­­­­Nk+1)

Применим алгоритм A к получившейся ДНФ G и вычислим |A(G)|. По лемме 2 |A(G)|  k  (D ≡ true)  (D ≡ false). Поскольку алгоритм A полиномиальный, мы можем вычислить значение утверждения (D ≡ true), то есть решить исходную задачу ВЫП за полином. В предположении, что P ≠ NP, приходим к противоречию.

Несуществование полиномиального алгоритма, решающего задачу МинЭквДНФ с точностью до мулитипликативной константы


Лемма 3: пусть дана некоторая ДНФ D(­x1, x2, …, xN), целое положительное число c, алгоритм B, принимающий на вход произвольную ДНФ D и возвращающий ДНФ, такой что:

  1. D ≡ B(D)

  2. |B(D)|  OPT(D) * c

Тогда: |B(D)| = 0  (D ≡ true)  (D ≡ false)

Доказательство:

: пусть (D ≡ true)  (D ≡ false). В таком случае OPT(D) = 0, а значит |B(D)|  OPT(D) * c = 0.

: пусть |A(D)| = 0. В таком случае, A(D) не зависит от своих переменных, то есть (B(D) ≡ true)  (B(D) ≡ false)  (D ≡ true)  (D ≡ false).

Теорема 2: В предположении, что P ≠ NP, не существует полиномиального алгоритма B, решающего задачу МинЭквДНФ, такого что  ДНФ D |A(D)|  OPT(D) * k, где k – фиксированное целое положительное число.

Доказательство: доказательство проведем от противного. Предположим, что существует некоторый полиномиальный алгоритм B и целое положительное число k, такие что  ДНФ D |B(D)|  OPT(D) + k. Построим полиномиальный алгоритм для решения задачи ВЫП.

Пусть дан экземляр задачи ВЫП: дана КНФ F(x1, x2, ..., x­­­­N), требуется выяснить, существует ли такой набор {σ­1, σ­2, ..., σ­N}, что F(σ­1, σ­2, ..., σ­N) = true. Построим ДНФ D = F. Данное построение делается за линейное время, с помощью правил (a & b) = a  b и (a  b) = a & b. F выполнима  (F ≡ false)  (D ≡ true). Утверждение (D ≡ false) можно проверить за полиномиальное время (по лемме 1). Вычислим |B(D)|. По лемме 3 |B(D)| = 0  (D ≡ true)  (D ≡ false). Поскольку алгоритм A полиномиальный, мы можем вычислить значение утверждения (D ≡ true), то есть решить исходную задачу ВЫП за полином. В предположении, что P ≠ NP, приходим к противоречию.

Частные случаи


Задачей МинЭквДНФ(K) назовем задачу МинЭквДНФ со следующим ограничением на входные данные – каждый дизъюнкт содержит не более K вхождений переменных.

МинЭквДНФ(1)


Теорема 3: существует полиномиальный алгоритм для решения задачи МинЭквДНФ(1).

Доказательство: для доказательства приведем указанный алгоритм.



Каждый дизъюнкт – это переменная или ее отрицание.

  1. Отсортируем дизъюнкты по индексу переменных.

  2. Разделим дизъюнкты на группы по индексам их переменных.

  3. Для каждой группы произведем следующее преобразование:

    1. Если группа содержит только вхождения переменной без отрицания, заменим ее на единственное вхождение этой переменной.
      x1  x1  …  x1  x1

    2. Если группа содержит только вхождения переменной с отрицания, заменим ее на единственное вхождение отрицания этой переменной.
      x1x1  …  x1x1

    3. Если группа содержит вхождения переменной как с отрицанием, так и без, то алгоритм заканчивается и возвращает true.

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

МинЭквДНФ(3)


Теорема 4: В предположении, что P ≠ NP, не существует полиномиального алгоритма решающего задачу МинЭквДНФ(3) с точностью до аддитивной или мультипликативной константы.

Доказательство: Для доказательства необходимо повторить рассуждения теорем 1 и 2, за исключением того, что в предположении существования указанного алгоритма, будет строиться полиномиальный алгоритм для решения задачи 3-ВЫП, вместо ВЫП. Но так как задача 3-ВЫП является NP-полной, получим противоречие.
скачать файл



Смотрите также: