Монотонная дуализация

В теоретической информатике монотонная дуализация — это вычислительная задача построения двойственной функции монотонной булевой функции . Эквивалентные задачи можно также сформулировать как построение трансверсального гиперграфа заданного гиперграфа , перечисление всех минимальных множеств попадания семейства множеств или перечисление всех минимальных покрытий множеств семейства множеств. Эти задачи могут быть решены за квазиполиномиальное время в объединенном размере его входа и выхода, но могут ли они быть решены за полиномиальное время — это открытая проблема.

Определения

Булева функция принимает в качестве входных данных присвоение значений истинности своим аргументам и выдает в качестве выходных данных другое значение истинности. Она монотонна, когда изменение аргумента с ложного на истинное не может изменить выход с истинного на ложное. Каждая монотонная булева функция может быть выражена как булево выражение, используя только логическую дизъюнкцию («или») и логическую конъюнкцию («и»), без использования логического отрицания («не»). Такое выражение называется монотонным булевым выражением. Каждое монотонное булевое выражение описывает монотонную булеву функцию. ^[1]

Для одной и той же функции может быть много различных выражений. Среди них есть два специальных выражения, конъюнктивная нормальная форма и дизъюнктивная нормальная форма . Для монотонных функций эти две специальные формы также могут быть ограничены монотонностью: ^[1]

• Конъюнктивная нормальная форма монотонной функции выражает функцию как конъюнкцию («и») предложений, каждое из которых является дизъюнкцией («или») некоторых переменных. Предложение может появляться в конъюнктивной нормальной форме, если оно истинно всякий раз, когда общая функция истинна; в этом случае оно называется импликатой , потому что истинность функции подразумевает истинность предложения. Это выражение можно сделать каноническим, ограничив его использованием только простых импликатов , импликатов, которые используют минимальный набор переменных. Конъюнктивная нормальная форма, использующая только простые импликат, называется простой КНФ . ^[1]
• Дизъюнктивная нормальная форма монотонной функции выражает функцию как дизъюнкцию («или») предложений, каждое из которых является конъюнкцией («и») переменных. Конъюнкция может появляться в дизъюнктивной нормальной форме, если она ложна всякий раз, когда общая функция ложна; в этом случае она называется импликантой , потому что ее истинность подразумевает истинность функции. Это выражение можно сделать каноническим, ограничив его использованием только простых импликантов , импликантов, которые используют минимальный набор переменных. Дизъюнктивная нормальная форма, использующая только простые импликанты, называется простой DNF . ^[1]

Двойственная булевой функции получается путем отрицания всех ее переменных, применения функции и последующего отрицания результата. Двойственная двойственной функции любой булевой функции является исходной функцией. Двойственная монотонной функции является монотонной. Если дано монотонное булево выражение, то замена всех конъюнкций дизъюнкциями дает другое монотонное булево выражение для двойственной функции, следуя законам Де Моргана . Однако это преобразует конъюнктивную нормальную форму в дизъюнктивную нормальную форму, и наоборот, что может быть нежелательным. Монотонная дуализация — это проблема нахождения выражения для двойственной функции без изменения формы выражения или, что эквивалентно, преобразования функции в одной нормальной форме в двойственную форму. ^[1]

Как функциональная проблема, монотонная дуализация может быть выражена следующими эквивалентными способами: ^{[1] [2]}

• Для данного (простого) выражения CNF постройте (простое) выражение CNF для двойственной функции. ^[1]
• Преобразовать (простое) выражение CNF функции в (простое) выражение DNF для той же функции, или наоборот ^[1]
• Построить трансверсальный гиперграф данного гиперграфа . Это гиперграф на том же множестве вершин, который имеет гиперребро для каждого минимального подмножества вершин, которое касается всех ребер данного гиперграфа. ^[1]
• Дано семейство множеств , сгенерировать все минимальные множества попадания семейства. Это множества элементов, которые включают по крайней мере один элемент из каждого множества и не имеют собственного подмножества с тем же свойством. Если множества в данном семействе интерпретируются как гиперребра в гиперграфе, их минимальные множества попадания являются гиперребрами трансверсального гиперграфа. ^[2]
• Дано семейство множеств, сгенерировать все минимальные покрытия множеств семейства. Покрытие множеств — это подсемейство с тем же объединением, что и все семейство. Если множества в данном семействе интерпретируются как вершины в гиперграфе, причем каждый элемент множеств интерпретируется как гиперребро, инцидентное множествам, содержащим этот элемент, то минимальные покрытия множеств являются гиперребрами трансверсального гиперграфа. ^[2]

Другая версия проблемы может быть сформулирована как проблема «точного обучения» в теории вычислительного обучения : имея доступ к подпрограмме для оценки монотонной булевой функции, реконструировать как CNF, так и DNF-представления функции, используя небольшое количество оценок функции. Однако при анализе сложности этой проблемы решающее значение имеет то, что выводятся как CNF, так и DNF-представления. Если выводится только CNF-представление неизвестной монотонной функции, из теории информации следует , что количество оценок функции иногда должно быть экспоненциальным в объединенных размерах ввода и вывода. Это происходит потому, что (чтобы быть уверенным в получении правильного ответа) алгоритм должен оценить функцию по крайней мере один раз для каждого простого импликата и по крайней мере один раз для каждого простого импликата, но это количество оценок может быть экспоненциально больше, чем количество простых импликат. ^[1]

Также возможно выразить вариант проблемы монотонной дуализации как проблему принятия решения с булевым ответом: ^[1]

• Проверьте, представляют ли два простых выражения CNF двойственные функции.
• Проверьте, представляют ли простое выражение CNF и простое выражение DNF одну и ту же функцию.

Нерешенная проблема в информатике :

Можно ли проверить, представляют ли два простых выражения CNF двойственные функции за полиномиальное время?

(еще нерешенные проблемы в информатике)

Открытой проблемой является то, имеет ли монотонная дуализация алгоритм полиномиального времени (в любой из этих эквивалентных форм). Самые быстрые известные алгоритмы работают за квазиполиномиальное время . ^[1] Размер выходных данных задач дуализации и точного обучения может быть экспоненциально большим, как функция количества переменных или размера входных данных. Например, граф с -вершинами, состоящий из непересекающихся треугольников, имеет гиперребра в своем трансверсальном гиперграфе. ^[3] Поэтому для этих задач требуется чувствительный к выходным данным алгоритм , который занимает небольшое количество времени на предложение выходных данных. Формулировки решения, дуализации и точного обучения задачи все вычислительно эквивалентны в следующем смысле: любая из них может быть решена с помощью подпрограммы для любой другой из этих задач с числом вызовов подпрограмм, которое является полиномиальным по объединенным размерам входных и выходных данных задач. ^[4] Поэтому, если бы любая из этих задач могла быть решена за полиномиальное время , они все могли бы. Однако наилучшая известная временная граница для этих задач — это квазиполиномиальное время . Остается открытым вопрос о том, можно ли решить их за полиномиальное время. ^[1] ${\displaystyle n}$ ${\displaystyle n/3}$ ${\displaystyle 3^{n/3}}$

Сложность вычислений

Эквивалентность решения, перечисления и точного обучения

Задача нахождения простого выражения CNF для двойственной функции монотонной функции, заданной в виде формулы CNF, может быть решена путем нахождения выражения DNF для заданной функции и его последующей дуализации. Следовательно, нахождение двойственного выражения CNF и нахождение выражения DNF для (первичной) заданной функции имеют одинаковую сложность. Эту задачу также можно рассматривать как частный случай точной формулировки задачи обучения. Из заданного выражения CNF легко вычислить функцию, которую оно выражает. Точный алгоритм обучения вернет как начальное выражение CNF, так и желаемое выражение DNF. Следовательно, дуализация не может быть сложнее точного обучения. ^[5]

Также просто решить задачу принятия решения, имея алгоритм для дуализации: дуализовать данное выражение CNF, а затем проверить, равно ли оно данному выражению DNF. Поэтому исследования в этой области были сосредоточены на другом направлении этой эквивалентности: решении точной задачи обучения (или задачи дуализации) с учетом подпрограммы для задачи принятия решения. ^[4]

Биох и Ибараки (1995) описывают следующий алгоритм решения задачи точного обучения с использованием подпрограммы принятия решений:

• Инициализируйте наборы простых предложений CNF и DNF, которые были идентифицированы к настоящему моменту, изначально пустыми.
• Повторите следующие шаги:
  • Используйте задачу принятия решения, чтобы проверить, являются ли текущие наборы простых предложений CNF и простых предложений DNF двойственными, и если это так, завершите алгоритм, вернув найденные предложения.
  • Построить истинностное назначение переменным, для которых значение функции не принудительно становится истинным ни известными простыми предложениями DNF, ни вынужденным быть ложным ни известными простыми предложениями CNF. Это построение может быть выполнено путем выбора значений для переменных по одному за раз, на каждом шаге используя проблему принятия решения для сохранения свойства, что предложения CNF и DNF являются недвойственными при ограничении выбранным истинностным назначением.
  • Оцените функцию при этом назначении истинности. Если это правда, попробуйте изменить переменные по одной с true на false, чтобы найти минимальное назначение истинности, для которого функция все еще оценивается как истина. Это минимальное назначение истинности соответствует простому предложению DNF, еще не известному; добавьте его к набору известных предложений.
  • Симметрично, если функция оценивается как false, то попробуйте изменить переменные по одной с false на true, чтобы найти максимальное назначение истинности, для которого функция все еще оценивается как false. Это максимальное назначение истинности соответствует простому предложению CNF, еще не известному; добавьте его к набору известных предложений.

Каждая итерация через внешний цикл алгоритма использует линейное число вызовов к проблеме принятия решения для нахождения невынужденного назначения истинности, использует линейное число оценок функции для нахождения минимального истинного или максимального ложного значения функции и добавляет одно предложение к выходу. Таким образом, общее число вызовов к проблеме принятия решения и общее число оценок функции являются полиномом общего размера выхода. ^[4]

Квазиполиномиальное время

Центральным результатом в исследовании этой проблемы Майклом Фредманом и Леонидом Хачияном является то, что монотонная дуализация (в любой из ее эквивалентных форм) может быть решена за квазиполиномиальное время . ^{[1] [6]} Их алгоритмы напрямую решают задачу принятия решения, но могут быть преобразованы в другие формы задачи монотонной дуализации, как описано в § Эквивалентность различных формулировок. В качестве альтернативы, в случаях, когда ответ на задачу принятия решения — нет, алгоритмы могут быть изменены для возврата свидетеля , то есть назначения истинности, для которого входные формулы не могут определить значение функции. Его основная идея заключается в том, чтобы сначала «очистить» экземпляр задачи принятия решения, удалив избыточную информацию и напрямую решив некоторые легко решаемые случаи задачи. Затем, в оставшихся случаях он разветвляется на тщательно выбранной переменной. Это означает рекурсивный вызов того же алгоритма для двух меньших подзадач, одной для ограниченной монотонной функции, для которой переменная была установлена ​​как истина, и другой, в которой переменная была установлена ​​как ложь. Шаг очистки обеспечивает существование переменной, принадлежащей многим предложениям, что приводит к значительному сокращению размера рекурсивной подзадачи. ^[1]

Более подробно, первый и более медленный из двух алгоритмов Фредмана и Хачияна выполняет следующие шаги: ^{[1] [6]}

• Удалите любое предложение, которое не является минимальным среди заданного набора предложений. (То есть удаленное предложение использует набор переменных, который является надмножеством переменных в другом предложении того же типа.)
• Если два набора предложений (CNF и DNF в одной версии задачи принятия решения или наборы предложений CNF, которые должны представлять две двойственные функции в другой версии) не охватывают одни и те же наборы переменных, вернуть сообщение о том, что они не являются двойственными.
• Если два предложения из разных наборов предложений используют непересекающиеся наборы переменных, вернуть, что они не являются дуальными. В этом случае предложения подразумевают противоречивые значения функции для любого назначения истинности, которое согласуется с ними обоими.
• Если какое-либо предложение в одном классе использует число переменных, превышающее число предложений в другом классе, вернуть, что они не являются двойственными. Если это предложение должно быть минимальным, то не может быть так, что удаление любой одной переменной из него создаст допустимое предложение для той же функции, но недостаточно предложений из другого класса, чтобы заблокировать каждое из этих удалений.
• Для каждого предложения подсчитайте количество истинностных назначений, значение функции которых определяется предложением. Это число равно , для предложения с переменными в задаче с переменными. Если сумма этих чисел, добавленная ко всем предложениям обоих типов, меньше истинностных назначений, которые существуют в общей сложности, то верните, что два набора предложений не являются двойственными: по крайней мере одно истинностное назначение должно иметь значение, которое они не определяют. ${\displaystyle 2^{n-k}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle 2^{n}}$
• Если какой-либо набор предложений пуст или оба состоят только из одного предложения, обработайте задачу как особый случай за постоянное время.
• В остальных случаях существует переменная, которая встречается в большой части одного из двух наборов предложений. Разветвляйтесь по этой переменной. Точнее, если есть полные предложения, то (чтобы охватить все назначения истинности) по крайней мере одно из предложений должно иметь не более переменных. Каждое предложение в другом наборе предложений должно иметь непустое пересечение с этим коротким предложением, поэтому одна из переменных в коротком предложении встречается по крайней мере в части другого набора предложений. ${\displaystyle m}$ ${\displaystyle \log _{2}m}$ ${\displaystyle 1/\log _{2}m}$

Когда этот алгоритм разветвляется на переменной, встречающейся во многих предложениях, эти предложения исключаются из одного из двух рекурсивных вызовов. Используя этот факт, время выполнения алгоритма может быть ограничено экспоненциальной функцией . ^{[1] [6]} ${\displaystyle (\log n)^{3}}$

Второй алгоритм Фредмана и Хачияна имеет схожую общую структуру, но в случае, когда переменная ветви встречается во многих предложениях одного набора и в нескольких других, он выбирает первый из двух рекурсивных вызовов как тот, где установка переменной ветви значительно сокращает количество предложений. Если этот рекурсивный вызов не находит несоответствия, то вместо выполнения одного рекурсивного вызова для другой ветви он выполняет один вызов для каждого предложения, содержащего переменную ветви, на ограниченной подзадаче, в которой все другие переменные этого предложения были назначены таким же образом. Его время выполнения является экспоненциальной функцией . ^{[1] [6]} ${\displaystyle (\log n)^{2}}$

Полиномиальные частные случаи

Было показано, что многие частные случаи задачи монотонной дуализации разрешимы за полиномиальное время посредством анализа их параметризованной сложности . ^[2] К ним относятся:

• Дуализация формул CNF или DNF, в которых каждая переменная появляется в ограниченном числе предложений, ^[7] или точное изучение монотонных функций, имеющих формулы этого типа. ^[8]
• Построение трансверсальных гиперграфов равномерно разреженных гиперграфов, в которых каждый индуцированный подгиперграф имеет ограниченную среднюю степень, ^[9] и гиперграфов, для которых обобщения теоретико-графовых понятий ширины дерева или вырожденности ограничены. ^[10]
• Построение трансверсальных гиперграфов, для которых дополнение (гиперграф, полученный путем дополнения каждого гиперребра) имеет низкую степень. ^[11]

Приложения

Одно из применений монотонной дуализации включает групповое тестирование для обнаружения и изоляции неисправностей в диагностике сложных систем на основе моделей . Из коллекции наблюдений за неисправным поведением системы, каждое из которых имеет некоторый набор активных компонентов, можно предположить, что неисправные компоненты, вызывающие это неправильное поведение, вероятно, образуют минимальный набор попаданий этого семейства наборов. ^{[2] [12]}

В биохимической инженерии перечисление множеств попаданий использовалось для идентификации подмножеств метаболических реакций, удаление которых из системы регулирует баланс системы в желаемом направлении. ^{[2] [13] [14]} Аналогичные методы также применялись к другим сетям биологических взаимодействий, например, при разработке экспериментов с микрочипами , которые можно использовать для вывода взаимодействий белков в биологических системах. ^[2]

В развлекательной математике , при разработке головоломок судоку , проблема проектирования системы подсказок, которая имеет заданную сетку чисел в качестве своего единственного решения, может быть сформулирована как задача минимального набора попаданий. 81 кандидат-подсказка из заданной сетки являются элементами, которые должны быть выбраны в наборе попаданий, а наборы, которые должны быть поражены, являются наборами кандидатов-подсказок, которые могут исключить каждое альтернативное решение. Таким образом, перечисление минимальных наборов попаданий может быть использовано для нахождения всех систем подсказок, которые имеют заданное решение. Этот подход был частью вычислительного доказательства того, что невозможно разработать правильную головоломку судоку, имея всего 16 подсказок. ^{[2] [15]}

Ссылки

1. Эйтер, Томас; Макино, Казухиса; Готтлоб, Георг (2008), «Вычислительные аспекты монотонной дуализации: краткий обзор», Дискретная прикладная математика , 156 (11): 2035–2049, doi : 10.1016/j.dam.2007.04.017 , MR  2437000
2. Гейнер-Дьюар, Эндрю; Вера-Ликона, Паола (2017), «Проблема генерации минимального множества попаданий: алгоритмы и вычисления», SIAM Journal on Discrete Mathematics , 31 (1): 63–100, arXiv : 1601.02939 , doi : 10.1137/15M1055024, MR  3590650
3. Moon, JW; Moser, L. (1965), «О кликах в графах», Israel Journal of Mathematics , 3 : 23–28, doi : 10.1007/BF02760024, MR  0182577, S2CID  9855414
4. Bioch, Jan C.; Ibaraki, Toshihide (1995), «Сложность идентификации и дуализации положительных булевых функций», Information and Computation , 123 (1): 50–63, doi : 10.1006/inco.1995.1157 , hdl : 1765/55247 , MR  1358967
5. Гурвич, В.; Хачиян, Л. (1999), «О генерации неизбыточных конъюнктивных и дизъюнктивных нормальных форм монотонных булевых функций», Дискретная прикладная математика , 96/97: 363–373, doi :10.1016/S0166-218X(99)00099-2, MR  1724731
6. Фредман, Майкл Л .; Хачиян, Леонид (1996), «О сложности дуализации монотонных дизъюнктивных нормальных форм», Журнал алгоритмов , 21 (3): 618–628, doi :10.1006/jagm.1996.0062, MR  1417667
7. Доминго, Карлос; Мишра, Нина; Питт, Леонард (1999), «Эффективная дуализация монотонной CNF/DNF с ограничением по чтению путем обучения с помощью запросов на членство», Машинное обучение , 37 (1): 89–110, doi : 10.1023/a:1007627028578
8. Мишра, Нина; Питт, Леонард (1997), «Генерация всех максимальных независимых множеств гиперграфов ограниченной степени», в Фройнд, Йоав ; Шапир, Роберт Э. (ред.), Труды Десятой ежегодной конференции по теории вычислительного обучения, COLT 1997, Нэшвилл, Теннесси, США, 6-9 июля 1997 г. , Ассоциация вычислительной техники, стр. 211–217, doi :10.1145/267460.267500
9. Хачиян, Леонид ; Борос, Эндре ; Гурвич, Владимир; Элбассиони, Халед (2007), «Вычисление множества максимальных независимых множеств для гиперграфов параллельно», Parallel Processing Letters , 17 (2): 141–152, doi :10.1142/S0129626407002934, MR  2334718
10. Эйтер, Томас; Готтлоб, Георг; Макино, Казухиса (2003), «Новые результаты по монотонной дуализации и генерации трансверсалей гиперграфов», SIAM Journal on Computing , 32 (2): 514–537, arXiv : cs/0204009 , doi :10.1137/S009753970240639X, MR  1969402
11. Elbassioni, Khaled M.; Hagen, Matthias; Rauf, Imran (2008), "Some fixed-parameter tractable classes of hypergraph duality and related problems", в Grohe, Martin; Niedermeier, Rolf (ред.), Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, 14-16 мая 2008 г. Труды , Lecture Notes in Computer Science, т. 5018, Springer, стр. 91–102, doi :10.1007/978-3-540-79723-4_10
12. Рейтер, Рэймонд (апрель 1987 г.), «Теория диагностики из первых принципов», Искусственный интеллект , 32 (1): 57–95, doi :10.1016/0004-3702(87)90062-2
13. Кламт, Штеффен; Жиль, Эрнст Дитер (январь 2004 г.), «Минимальные наборы разрезов в сетях биохимических реакций», Биоинформатика , 20 (2): 226–234, doi : 10.1093/bioinformatics/btg395
14. Хаус, Утц-Уве; Кламт, Штеффен; Стивен, Тамон (апрель 2008 г.), «Вычислительные стратегии нокаута в метаболических сетях», Журнал вычислительной биологии , 15 (3): 259–268, arXiv : 0801.0082 , doi : 10.1089/cmb.2007.0229
15. МакГвайр, Гэри; Тугеманн, Бастиан; Сиварио, Жиль (2014), «Судоку с 16 подсказками не существует: решение проблемы минимального количества подсказок в судоку с помощью перечисления множества попаданий», Experimental Mathematics , 23 (2): 190–217, arXiv : 1201.0749 , doi :10.1080/10586458.2013.870056, MR  3223774