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

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

Определения

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

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

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

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

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

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

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

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

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

Нерешенная задача в информатике :

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

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

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

Вычислительная сложность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р Эйтер, Томас; Макино, Казухиса; Готтлоб, Георг (2008), «Вычислительные аспекты монотонной дуализации: краткий обзор», Discrete Applied Mathematics , 156 (11): 2035–2049, doi : 10.1016/j.dam.2007.04.017 , MR 2437000
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Гейнер-Дьюар, Эндрю; Вера-Ликона, Паола (2017), «Проблема генерации минимального набора попаданий: алгоритмы и вычисления», SIAM Journal on Discrete Mathematics , 31 (1): 63–100, arXiv : 1601.02939 , doi : 10.1137/15M1055024 , MR 3590650
^ Мун, Дж.В.; Мозер, Л. (1965), «О кликах в графах», Израильский математический журнал , 3 : 23–28, doi : 10.1007/BF02760024 , MR 0182577 , S2CID 9855414
^ Jump up to: ^а ^б ^с Биох, Ян К.; Ибараки, Тошихидэ (1995), «Сложность идентификации и дуализации положительных булевых функций», Information and Computation , 123 (1): 50–63, doi : 10.1006/inco.1995.1157 , hdl : 1765/55247 , MR 1358967
^ Гурвич В.; Хачиян, Л. (1999), «О порождении неизбыточных конъюнктивных и дизъюнктивных нормальных форм монотонных булевых функций», Discrete Applied Mathematics , 96/97: 363–373, doi : 10.1016/S0166-218X(99)00099-2 , МР 1724731
^ Jump up to: ^а ^б ^с ^д Фредман, Майкл Л .; Хачиян, Леонид (1996), «О сложности дуализации монотонных дизъюнктивных нормальных форм», Журнал алгоритмов , 21 (3): 618–628, doi : 10.1006/jagm.1996.0062 , MR 1417667
^ Доминго, Карлос; Мишра, Нина; Питт, Леонард (1999), «Эффективная монотонная дуализация CNF/DNF с ограниченным чтением путем обучения с помощью запросов членства», Machine Learning , 37 (1): 89–110, doi : 10.1023/a:1007627028578
^ Мишра, Нина; Питт, Леонард (1997), «Генерация всех максимальных независимых наборов гиперграфов ограниченной степени», у Фрейнда, Йоав ; Шапир, Роберт Э. (ред.), Труды десятой ежегодной конференции по теории вычислительного обучения, COLT 1997, Нэшвилл, Теннесси, США, 6–9 июля 1997 г. , Ассоциация вычислительной техники, стр. 211–217, doi : 10.1145/267460.267500
^ Хачиян Леонид ; Борос, Эндре ; Гурвич Владимир; Эльбассиони, Халед (2007), «Параллельное вычисление множества максимальных независимых наборов для гиперграфов», Parallel Processing Letters , 17 (2): 141–152, doi : 10.1142/S0129626407002934 , MR 2334718
^ Эйтер, Томас; Готтлоб, Георг; Макино, Казухиса (2003), «Новые результаты по монотонной дуализации и генерации трансверсалей гиперграфов», SIAM Journal on Computing , 32 (2): 514–537, arXiv : cs/0204009 , doi : 10.1137/S009753970240639X , MR 1969402
^ Эльбасиони, Халед М.; Хаген, Матиас; Рауф, Имран (2008), «Некоторые управляемые классы двойственности гиперграфов с фиксированными параметрами и связанные с ними проблемы», Гроэ, Мартин; Нидермейер, Рольф (ред.), Параметризованные и точные вычисления, Третий международный семинар, IWPEC 2008, Виктория, Канада, 14-16 мая 2008 г. Труды , конспекты лекций по информатике, том. 5018, Springer, стр. 91–102, номер документа : 10.1007/978-3-540-79723-4_10.
^ Рейтер, Раймонд (апрель 1987 г.), «Теория диагностики на основе первых принципов», Искусственный интеллект , 32 (1): 57–95, doi : 10.1016/0004-3702(87)90062-2
^ Кламт, Штеффен; Жиль, Эрнст Дитер (январь 2004 г.), «Минимальные наборы сокращений в сетях биохимических реакций», Bioinformatics , 20 (2): 226–234, doi : 10.1093/bioinformatics/btg395
^ Хаус, Утц-Уве; Кламт, Штеффен; Стивен, Тэймон (апрель 2008 г.), «Вычисление стратегий выключения в метаболических сетях», Journal of Computational Biology , 15 (3): 259–268, arXiv : 0801.0082 , doi : 10.1089/cmb.2007.0229
^ Макгуайр, Гэри; Тугеманн, Бастиан; Чиварио, Жиль (2014), «Не существует судоку с 16 подсказками: решение проблемы минимального количества подсказок в судоку путем перечисления множества», Experimental Mathematics , 23 (2): 190–217, arXiv : 1201.0749 , doi : 10.1080/ 10586458.2013.870056 , МР 3223774

[emg-survey-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р Эйтер, Томас; Макино, Казухиса; Готтлоб, Георг (2008), «Вычислительные аспекты монотонной дуализации: краткий обзор», Discrete Applied Mathematics , 156 (11): 2035–2049, doi : 10.1016/j.dam.2007.04.017 , MR 2437000

[gv-hitting-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Гейнер-Дьюар, Эндрю; Вера-Ликона, Паола (2017), «Проблема генерации минимального набора попаданий: алгоритмы и вычисления», SIAM Journal on Discrete Mathematics , 31 (1): 63–100, arXiv : 1601.02939 , doi : 10.1137/15M1055024 , MR 3590650

[mm-cliques-3] Мун, Дж.В.; Мозер, Л. (1965), «О кликах в графах», Израильский математический журнал , 3 : 23–28, doi : 10.1007/BF02760024 , MR 0182577 , S2CID 9855414

[bi-identification-4] Jump up to: ^а ^б ^с Биох, Ян К.; Ибараки, Тошихидэ (1995), «Сложность идентификации и дуализации положительных булевых функций», Information and Computation , 123 (1): 50–63, doi : 10.1006/inco.1995.1157 , hdl : 1765/55247 , MR 1358967

[gk-irredundant-5] Гурвич В.; Хачиян, Л. (1999), «О порождении неизбыточных конъюнктивных и дизъюнктивных нормальных форм монотонных булевых функций», Discrete Applied Mathematics , 96/97: 363–373, doi : 10.1016/S0166-218X(99)00099-2 , МР 1724731

[fk-quasipolynomial-6] Jump up to: ^а ^б ^с ^д Фредман, Майкл Л .; Хачиян, Леонид (1996), «О сложности дуализации монотонных дизъюнктивных нормальных форм», Журнал алгоритмов , 21 (3): 618–628, doi : 10.1006/jagm.1996.0062 , MR 1417667

[dmp-read-restricted-7] Доминго, Карлос; Мишра, Нина; Питт, Леонард (1999), «Эффективная монотонная дуализация CNF/DNF с ограниченным чтением путем обучения с помощью запросов членства», Machine Learning , 37 (1): 89–110, doi : 10.1023/a:1007627028578

[mp-independent-8] Мишра, Нина; Питт, Леонард (1997), «Генерация всех максимальных независимых наборов гиперграфов ограниченной степени», у Фрейнда, Йоав ; Шапир, Роберт Э. (ред.), Труды десятой ежегодной конференции по теории вычислительного обучения, COLT 1997, Нэшвилл, Теннесси, США, 6–9 июля 1997 г. , Ассоциация вычислительной техники, стр. 211–217, doi : 10.1145/267460.267500

[kbge-parallel-9] Хачиян Леонид ; Борос, Эндре ; Гурвич Владимир; Эльбассиони, Халед (2007), «Параллельное вычисление множества максимальных независимых наборов для гиперграфов», Parallel Processing Letters , 17 (2): 141–152, doi : 10.1142/S0129626407002934 , MR 2334718

[egm-results-10] Эйтер, Томас; Готтлоб, Георг; Макино, Казухиса (2003), «Новые результаты по монотонной дуализации и генерации трансверсалей гиперграфов», SIAM Journal on Computing , 32 (2): 514–537, arXiv : cs/0204009 , doi : 10.1137/S009753970240639X , MR 1969402

[ehr-fixed-11] Эльбасиони, Халед М.; Хаген, Матиас; Рауф, Имран (2008), «Некоторые управляемые классы двойственности гиперграфов с фиксированными параметрами и связанные с ними проблемы», Гроэ, Мартин; Нидермейер, Рольф (ред.), Параметризованные и точные вычисления, Третий международный семинар, IWPEC 2008, Виктория, Канада, 14-16 мая 2008 г. Труды , конспекты лекций по информатике, том. 5018, Springer, стр. 91–102, номер документа : 10.1007/978-3-540-79723-4_10.

[r-diagnosis-12] Рейтер, Раймонд (апрель 1987 г.), «Теория диагностики на основе первых принципов», Искусственный интеллект , 32 (1): 57–95, doi : 10.1016/0004-3702(87)90062-2

[kg-biochemical-13] Кламт, Штеффен; Жиль, Эрнст Дитер (январь 2004 г.), «Минимальные наборы сокращений в сетях биохимических реакций», Bioinformatics , 20 (2): 226–234, doi : 10.1093/bioinformatics/btg395

[hks-knockout-14] Хаус, Утц-Уве; Кламт, Штеффен; Стивен, Тэймон (апрель 2008 г.), «Вычисление стратегий выключения в метаболических сетях», Journal of Computational Biology , 15 (3): 259–268, arXiv : 0801.0082 , doi : 10.1089/cmb.2007.0229

[mtc-sudoku-15] Макгуайр, Гэри; Тугеманн, Бастиан; Чиварио, Жиль (2014), «Не существует судоку с 16 подсказками: решение проблемы минимального количества подсказок в судоку путем перечисления множества», Experimental Mathematics , 23 (2): 190–217, arXiv : 1201.0749 , doi : 10.1080/ 10586458.2013.870056 , МР 3223774

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]