2-выполнимость

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

Примеры проблемы 2-выполнимости обычно выражаются в виде булевых формул специального типа, называемых конъюнктивной нормальной формой (2-CNF) или формулами Крома . В качестве альтернативы они могут быть выражены как специальный тип ориентированного графа , граф импликации , который выражает переменные экземпляра и их отрицания как вершины в графе, а ограничения на пары переменных как направленные ребра. Оба этих типа входных данных могут быть решены за линейное время либо методом, основанным на отслеживании с возвратом, либо с использованием сильно связанных компонентов графа импликации. Разрешение, метод объединения пар ограничений для создания дополнительных допустимых ограничений, также приводит к полиномиальному временному решению. Проблемы 2-выполнимости обеспечивают один из двух основных подклассов формул конъюнктивной нормальной формы, которые могут быть решены за полиномиальное время; другой из двух подклассов - выполнимость по Хорну .

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

В теории сложности вычислений 2-выполнимость представляет собой пример NL-полной проблемы, которая может быть решена недетерминированно с использованием логарифмического объема памяти и является одной из самых сложных проблем, решаемых в рамках этой границы ресурса. Множеству всех решений для случая 2-выполнимости может быть задана структура медианного графа , но подсчет этих решений является # P-полным.и поэтому не ожидается получения решения за полиномиальное время. Случайные экземпляры претерпевают резкий фазовый переход от разрешимых экземпляров к неразрешимым по мере того, как отношение ограничений к переменным увеличивается после 1, явление предполагаемое, но недоказанное для более сложных форм проблемы выполнимости. Сложный в вычислительном отношении вариант 2-выполнимости, нахождение присвоения истинности, которое максимизирует количество удовлетворяемых ограничений, имеет алгоритм аппроксимации , оптимальность которого зависит от гипотезы уникальных игр , и еще один сложный вариант, нахождение удовлетворительного назначения, минимизирующего количество истинных переменных. - важный тестовый пример для параметризованной сложности .

Представления о проблемах [ править ]

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

${\ displaystyle (x_ {0} \ lor x_ {2}) \ land (x_ {0} \ lor \ lnot x_ {3}) \ land (x_ {1} \ lor \ lnot x_ {3}) \ land ( x_ {1} \ lor \ lnot x_ {4}) \ land}$

${\displaystyle (x_{2}\lor \lnot x_{4})\land {}(x_{0}\lor \lnot x_{5})\land (x_{1}\lor \lnot x_{5})\land (x_{2}\lor \lnot x_{5})\land }$

${\displaystyle (x_{3}\lor x_{6})\land (x_{4}\lor x_{6})\land (x_{5}\lor x_{6}).}$

Проблема 2-выполнимости состоит в том, чтобы найти присвоение истинности этим переменным, которое делает всю формулу истинной. Такое присваивание выбирает, делать ли каждую из переменных истинной или ложной, так что по крайней мере один литерал в каждом предложении становится истинным. Для показанного выше выражения одно из возможных удовлетворяющих присваиваний - это то, которое устанавливает для всех семи переменных значение true. Каждое предложение имеет по крайней мере одну неотрицательную переменную, поэтому это присвоение удовлетворяет каждому предложению. Есть также 15 других способов установить все переменные, чтобы формула стала истинной. Следовательно, экземпляр 2-выполнимости, представленный этим выражением, является выполнимым.

Формулы в этой форме известны как формулы 2-CNF. «2» в этом имени обозначает количество литералов в предложении, а «CNF» обозначает конъюнктивную нормальную форму , тип логического выражения в форме конъюнкции дизъюнкций. ^[1] Их также называют формулами Крома, в честь работы математика из Калифорнийского университета в Дэвисе Мелвена Р. Крома, чья статья 1967 года была одной из самых ранних работ по проблеме 2-выполнимости. ^[2]

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

${\displaystyle (x_{0}\lor \lnot x_{3})\;\equiv \;(\lnot x_{0}\Rightarrow \lnot x_{3})\;\equiv \;(x_{3}\Rightarrow x_{0}).}$

Из-за этой эквивалентности между этими различными типами операций экземпляр 2-выполнимости также может быть записан в импликативной нормальной форме , в которой мы заменяем каждое предложение or в конъюнктивной нормальной форме двумя импликациями, которым оно эквивалентно. ^[3]

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

Алгоритмы [ править ]

Известно несколько алгоритмов решения проблемы 2-выполнимости. Наиболее эффективные из них занимают линейное время . ^{[2] [4] [5]}

Разрешение и переходное закрытие [ править ]

Кром (1967) описал следующую процедуру решения за полиномиальное время для решения случаев 2-выполнимости. ^[2]

Предположим, что экземпляр 2-выполнимости содержит два предложения, в каждом из которых используется одна и та же переменная x , но что x инвертируется в одном предложении, а не в другом. Затем два предложения могут быть объединены для получения третьего предложения, имеющего два других литерала в двух предложениях; это третье предложение также должно выполняться, когда удовлетворяются оба первых два предложения. Например, мы можем объединить предложения и таким образом создать предложение . В терминах импликативной формы формулы 2-CNF это правило сводится к обнаружению двух импликаций и к выводу посредством транзитивности третьей импликации . ^[2]${\displaystyle (a\lor b)}$${\displaystyle (\lnot b\lor \lnot c)}$${\displaystyle (a\lor \lnot c)}$${\displaystyle \lnot a\Rightarrow b}$${\displaystyle b\Rightarrow \lnot c}$${\displaystyle \lnot a\Rightarrow \lnot c}$

Кром пишет, что формула является непротиворечивой, если повторное применение этого правила вывода не может генерировать одновременно предложения и для любой переменной . Как он доказывает, формула 2-CNF выполнима тогда и только тогда, когда она непротиворечива. Ведь, если формула несовместима, невозможно удовлетворить оба пункта и одновременно. И, если это непротиворечиво, то формулу можно расширить, многократно добавляя одно предложение формы или${\displaystyle (x\lor x)}$${\displaystyle (\lnot x\lor \lnot x)}$${\displaystyle x}$${\displaystyle (x\lor x)}$${\displaystyle (\lnot x\lor \lnot x)}$${\displaystyle (x\lor x)}$${\displaystyle (\lnot x\lor \lnot x)}$за один раз, сохраняя согласованность на каждом шаге, пока не будет включено такое предложение для каждой переменной. На каждом из этих шагов расширения одно из этих двух предложений всегда может быть добавлено с сохранением согласованности, поскольку в противном случае другое предложение может быть сгенерировано с использованием правила вывода. Как только все переменные имеют предложение этой формы в формуле, можно сгенерировать удовлетворительное присвоение всех переменных, установив для переменной значение true, если формула содержит предложение, и установив для нее значение false, если формула содержит предложение . ^[2]${\displaystyle x}$${\displaystyle (x\lor x)}$${\displaystyle (\lnot x\lor \lnot x)}$

Крома интересовала в первую очередь полнота систем правил вывода, а не эффективность алгоритмов. Однако его метод приводит к полиномиальной оценке времени для решения задач 2-выполнимости. Сгруппировав вместе все предложения, использующие одну и ту же переменную, и применив правило вывода к каждой паре предложений, можно найти все выводы, которые возможны из данного экземпляра 2-CNF, и проверить его согласованность, за общее время O ( n ³ ) , где n - количество переменных в экземпляре. Эта формула получена путем умножения количества переменных на O ( n ² )количество пар предложений, включающих данную переменную, к которым может быть применено правило вывода. Таким образом, можно определить, является ли данный экземпляр 2-CNF выполнимым за время O ( n ³ ) . Поскольку поиск удовлетворительного задания с использованием метода Крома включает в себя последовательность проверок согласованности O ( n ) , это займет время O ( n ⁴ ) . Даже Итаи и Шамир (1976) цитируют более быструю временную границу O ( n ² ) для этого алгоритма, основанную на более тщательном упорядочивании его операций. Тем не менее, даже эта меньшая временная граница была значительно улучшена более поздними алгоритмами линейного времениЭвен, Итаи и Шамир (1976) и Аспвалл, Пласс и Тарджан (1979) .

В терминах импликационного графа экземпляра 2-выполнимости правило вывода Крома можно интерпретировать как построение транзитивного замыкания графа. Как отмечает Кук (1971) , его также можно рассматривать как пример алгоритма Дэвиса – Патнэма для решения проблем выполнимости с использованием принципа разрешения . Его правильность следует из более общей правильности алгоритма Дэвиса – Патнэма. Его полиномиальная временная граница следует из того факта, что каждый шаг разрешения увеличивает количество клозов в экземпляре, которое ограничено сверху квадратичной функцией количества переменных. ^[6]

Ограниченный возврат [ править ]

Эвен Итаи и Шамир (1976) описывают методику, включающую ограниченный поиск с возвратом для решения проблем удовлетворения ограничений с помощью двоичных переменных и парных ограничений. Они применяют эту технику к задаче составления расписания занятий, но они также отмечают, что она применима и к другим задачам, включая 2-SAT. ^[5]

Основная идея их подхода - построить частичное присвоение истинности, по одной переменной за раз. Определенные шаги алгоритмов являются «точками выбора», точками, в которых переменной может быть присвоено одно из двух разных значений истинности, а более поздние шаги в алгоритме могут привести к возврату к одной из этих точек выбора. Однако можно вернуться только к самому последнему выбору. Все варианты, сделанные ранее, чем последний, являются постоянными. ^[5]

Изначально точки выбора нет, и все переменные не присвоены. На каждом шаге алгоритм выбирает переменную, значение которой нужно установить, следующим образом:

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

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

Even et al. не описал подробно, как эффективно реализовать этот алгоритм. Они заявляют только, что «используя соответствующие структуры данных для поиска последствий любого решения», каждый шаг алгоритма (кроме обратного отслеживания) может быть выполнен быстро. Однако некоторые входные данные могут привести к тому, что алгоритм будет возвращаться много раз, каждый раз выполняя много шагов перед возвратом, поэтому его общая сложность может быть нелинейной. Чтобы избежать этой проблемы, они модифицируют алгоритм таким образом, чтобы после достижения каждой точки выбора он начинал одновременно тестировать оба из двух назначений для переменной, установленной в точке выбора, затрачивая равное количество шагов на каждое из двух назначений. Как только тест для одного из этих двух назначений создаст другую точку выбора, другой тест останавливается,так что на любом этапе алгоритма есть только две ветви дерева поиска с возвратом, которые все еще тестируются. Таким образом, общее время, затраченное на выполнение двух тестов для любой переменной, пропорционально количеству переменных и пунктов входной формулы, значения которых присвоены постоянно. В результате алгоритм принимаетлинейное время в целом. ^[5]

Сильно связанные компоненты [ править ]

Аспвалл, Пласс и Тарьян (1979) нашли более простую процедуру с линейным временем для решения случаев 2-выполнимости, основанную на понятии сильно связных компонентов из теории графов . ^[4]

Две вершины ориентированного графа называются сильно связанными друг с другом, если существует направленный путь от одной к другой и наоборот. Это отношение эквивалентности , и вершины графа могут быть разбиты на компоненты сильной связности, подмножества, внутри которых каждые две вершины сильно связаны. Существует несколько эффективных алгоритмов линейного времени для поиска сильно связанных компонентов графа, основанных на поиске в глубину : алгоритм сильносвязных компонентов Тарьяна ^[7] и алгоритм сильных компонентов, основанный на путях ^[8], каждый выполняет одиночный поиск в глубину. Алгоритм Косараджу выполняет два поиска в глубину, но он очень прост.

С точки зрения графа импликации, два литерала принадлежат одному и тому же компоненту сильной связности, если существуют цепочки импликаций от одного литерала к другому и наоборот. Следовательно, два литерала должны иметь одинаковое значение в любом удовлетворительном присвоении данному экземпляру 2-выполнимости. В частности, если переменная и ее отрицание принадлежат одному и тому же компоненту с сильной связью, экземпляр не может быть удовлетворен, потому что невозможно присвоить обоим этим литералам одно и то же значение. Aspvall et al. Как было показано, это необходимое и достаточное условие : формула 2-КНФ выполнима тогда и только тогда, когда нет переменной, принадлежащей той же сильносвязной компоненте, что и ее отрицание. ^[4]

Это немедленно приводит к алгоритму линейного времени для проверки выполнимости формул 2-CNF: просто выполните строгий анализ связности на графе импликации и проверьте, что каждая переменная и ее отрицание принадлежат разным компонентам. Однако, как отмечает Aspvall et al. Также было показано, что это также приводит к алгоритму линейного времени для поиска удовлетворительного задания, если оно существует. Их алгоритм выполняет следующие шаги:

• Постройте граф импликации экземпляра и найдите его компоненты с сильной связью, используя любой из известных алгоритмов линейного времени для анализа сильной связности.
• Проверьте, содержит ли какой-либо сильно связанный компонент как переменную, так и ее отрицание. Если да, сообщите, что экземпляр не подходит и остановитесь.
• Постройте уплотнение графа импликации, меньший граф, который имеет одну вершину для каждой сильно связной компоненты и ребро от компонента i к компоненту j, если граф импликации содержит ребро uv такое, что u принадлежит компоненту i, а v принадлежит компоненту j . Сгущение автоматически является ориентированным ациклическим графом и, как и граф импликации, из которого он был сформирован, является кососимметричным .
• Топологически упорядочить вершины сгущения. На практике это может быть эффективно достигнуто как побочный эффект предыдущего шага, поскольку компоненты генерируются алгоритмом Косараджу в топологическом порядке и алгоритмом Тарьяна в обратном топологическом порядке. ^[9]
• Для каждого компонента в обратном топологическом порядке, если его переменные еще не имеют присвоений истинности, установите все литералы в компоненте как истинные. Это также приводит к тому, что для всех литералов в дополнительном компоненте устанавливается значение false.

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

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

Приложения [ править ]

Бесконфликтное размещение геометрических объектов [ править ]

Ряд точных и приближенных алгоритмов для задачи автоматического размещения этикеток основан на 2-выполнимости. Эта проблема касается размещения текстовых меток на элементах диаграммы или карты. Как правило, набор возможных местоположений для каждой надписи сильно ограничен не только самой картой (каждая метка должна быть рядом с объектом, который она маркирует, и не должна закрывать другие объекты), но и друг другом: каждые две надписи должны избегать перекрытия. друг друга, иначе они стали бы неразборчивыми. В общем, найти размещение метки, которое подчиняется этим ограничениям, является NP-сложной задачей.проблема. Однако, если у каждого объекта есть только два возможных местоположения для его метки (скажем, влево и вправо от объекта), то размещение метки может быть решено за полиномиальное время. Ведь в этом случае можно создать экземпляр 2-выполнимости, который имеет переменную для каждой метки и имеет предложение для каждой пары меток, которые могут перекрываться, предотвращая присвоение им перекрывающихся позиций. Если все метки являются конгруэнтными прямоугольниками, можно показать, что соответствующий экземпляр 2-выполнимости имеет только линейное количество ограничений, что приводит к почти линейным временным алгоритмам для поиска меток. ^[10] Пун, Чжу и Чин (1998)описать проблему маркировки карты, в которой каждая метка представляет собой прямоугольник, который может быть размещен в одном из трех положений относительно сегмента линии, который он маркирует: он может иметь сегмент в качестве одной из его сторон, или он может быть центрирован на сегменте . Они представляют эти три позиции с использованием двух бинарных переменных таким образом, что снова проверка существования действительной маркировки становится проблемой 2-выполнимости. ^[11]

Formann & Wagner (1991) используют 2-выполнимость как часть алгоритма аппроксимациидля задачи поиска квадратных меток максимально возможного размера для заданного набора точек с ограничением, что каждая метка имеет один из своих углов в точке, которую она маркирует. Чтобы найти метку заданного размера, они удаляют квадраты, которые, если их удвоить, перекрывают другую точку, и они исключают точки, которые могут быть помечены способом, который не может перекрываться с меткой другой точки. Они показывают, что эти правила исключения приводят к тому, что оставшиеся точки имеют только два возможных размещения меток на точку, позволяя найти допустимое размещение меток (если оно существует) в качестве решения для случая 2-выполнимости. Путем поиска самого большого размера метки, который приводит к разрешимому экземпляру 2-выполнимости, они находят допустимое размещение метки, размеры меток которого как минимум вдвое меньше оптимального решения. Этокоэффициент аппроксимации их алгоритма не более двух. ^{[10] [12]} Точно так же, если каждая метка прямоугольная и должна быть размещена таким образом, чтобы точка, которую она маркирует, находилась где-то вдоль ее нижнего края, тогда с помощью 2-выполнимости найти самый большой размер метки, для которого существует решение в котором каждая метка имеет точку в нижнем углу, дает коэффициент аппроксимации не более двух. ^[13]

Аналогичные применения 2-выполнимости были сделаны для других задач геометрического размещения. При рисовании графа , если положения вершин фиксированы и каждое ребро должно быть нарисовано как дуга окружности с одним из двух возможных положений (например, как дуговая диаграмма ), тогда возникает проблема выбора, какую дугу использовать для каждого ребра, чтобы Избегать пересечений - это проблема 2-выполнимости с переменной для каждого ребра и ограничением для каждой пары размещений, которые могут привести к пересечению. Однако в этом случае можно ускорить решение по сравнению с алгоритмом, который строит, а затем ищет явное представление графа импликации, путем неявного поиска в графе . ^[14] В СБИСпроектирование интегральной схемы: если набор модулей должен быть соединен проводами, каждый из которых может изгибаться не более одного раза, то опять же есть два возможных маршрута для проводов и проблема выбора, какой из этих двух маршрутов использовать, таким образом что все провода могут быть проложены в одном слое схемы, может быть решена как 2-выполнимый пример. ^[15]

Boros et al. (1999) рассматривают другую проблему проектирования СБИС: вопрос о том, нужно ли зеркально перевернуть каждый модуль в схеме. Этот зеркальный поворот оставляет операции модуля неизменными, но меняет порядок точек, в которых входные и выходные сигналы модуля подключаются к нему, возможно, изменяя то, насколько хорошо модуль вписывается в остальную конструкцию. Boros et al.рассмотрим упрощенную версию задачи, в которой модули уже размещены вдоль одного линейного канала, в котором провода между модулями должны быть проложены, и существует фиксированный предел плотности канала (максимальное количество сигналов, которые должен проходить через любое поперечное сечение канала). Они отмечают, что эта версия проблемы может быть решена как пример 2-выполнимости, в котором ограничения связывают ориентации пар модулей, которые находятся непосредственно через канал друг от друга. Как следствие, оптимальная плотность также может быть эффективно вычислена путем выполнения двоичного поиска, в котором каждый шаг включает решение экземпляра 2-выполнимости. ^[16]

Кластеризация данных [ править ]

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

Тот же метод также можно использовать в качестве подпрограммы, когда диаметры отдельных кластеров неизвестны. Чтобы проверить, может ли быть достигнута заданная сумма диаметров, не зная диаметров отдельных кластеров, можно попробовать все максимальные пары целевых диаметров, которые в сумме составляют не более заданной суммы, представляя каждую пару диаметров как экземпляр 2-выполнимости и используя алгоритм 2-выполнимости, чтобы определить, может ли эта пара быть реализована путем кластеризации. Чтобы найти оптимальную сумму диаметров, можно выполнить двоичный поиск, в котором каждый шаг является проверкой выполнимости этого типа. Тот же подход также работает для поиска кластеров, которые оптимизируют другие комбинации, кроме сумм диаметров кластеров, и которые используют произвольные числа несходства (а не расстояния в метрическом пространстве) для измерения размера кластера. ^[17]Временная граница для этого алгоритма определяется временем решения последовательности двух экземпляров выполнимости, которые тесно связаны друг с другом, и Рамнат (2004) показывает, как решить эти связанные экземпляры быстрее, чем если бы они решались независимо от каждого из них. другое, что приводит к общему ограничению времени O ( n ³ ) для задачи кластеризации суммы диаметров. ^[18]

Планирование [ править ]

Даже Итаи и Шамир (1976) рассматривают модель расписания занятий, в которой группа из n учителей должна быть запланирована для обучения каждой из m групп учеников. Количество часов в неделю, которые учитель i проводит с когортой j , описывается записью R _ij матрицы R, заданной в качестве входных данных для задачи, и у каждого учителя также есть набор часов, в течение которых он или она доступны для планирования. Как они показывают, проблема NP-полная., даже когда у каждого учителя есть не более трех свободных часов, но это может быть решено как пример 2-выполнимости, когда у каждого учителя есть только два свободных часа. (Учителей, у которых есть только один доступный час, можно легко исключить из задачи.) В этой задаче каждая переменная v _ij соответствует часу, который учитель i должен провести с когортой j , присвоение переменной указывает, является ли этот час первым. или второй из доступных часов учителя, и есть пункт о 2-выполнимости, предотвращающий любой конфликт любого из двух типов: две когорты, назначенные учителю одновременно, друг с другом, или одна когорта, назначенная двум учителям одновременно время. ^[5]

Миясиро и Мацуи (2005) применяют 2-выполнимость к задаче спортивного расписания, в которой пары кругового турнирауже выбраны, и игры должны быть назначены на стадионы команд. В этой задаче желательно по возможности чередовать домашние и выездные игры, избегая «перерывов», в которых команда играет две домашние игры подряд или две выездные игры подряд. Максимум две команды могут полностью избежать перерывов, чередуя домашние и выездные игры; ни одна другая команда не может иметь такое же расписание домашних матчей, как эти две, потому что тогда она не сможет играть с командой, с которой у нее было такое же расписание. Таким образом, в оптимальном расписании есть две команды без перерыва и по одному перерыву для всех остальных команд. После того, как выбрана одна из команд без перерыва, можно создать задачу о 2-выполнимости, в которой каждая переменная представляет собой домашнее задание для одной команды в одной игре.и ограничения обеспечивают выполнение свойств, согласно которым любые две команды имеют согласованное назначение для своих игр, что у каждой команды есть не более одного перерыва до и не более одного перерыва после игры с безбарьерной командой, и что ни у одной команды нет двух перерывов. Следовательно, проверка того, допускает ли расписание решение с оптимальным количеством перерывов, может быть проведена путем решения линейного числа задач 2-выполнимости, по одной на каждый выбор непобедимой команды. Подобный метод также позволяет находить расписания, в которых у каждой команды есть один перерыв, и максимизировать, а не минимизировать количество перерывов (чтобы уменьшить общий пробег, пройденный командами).Проверка того, допускает ли расписание решение с оптимальным количеством перерывов, может быть проведена путем решения линейного числа задач с двумя задачами выполнимости, по одной на каждый выбор группы без перерывов. Подобный метод также позволяет находить расписания, в которых у каждой команды есть один перерыв, и максимизировать, а не минимизировать количество перерывов (чтобы уменьшить общий пробег, пройденный командами).Проверка того, допускает ли расписание решение с оптимальным количеством перерывов, может быть проведена путем решения линейного числа задач с двумя задачами выполнимости, по одной на каждый выбор группы без перерывов. Подобный метод также позволяет находить расписания, в которых у каждой команды есть один перерыв, и максимизировать, а не минимизировать количество перерывов (чтобы уменьшить общий пробег, пройденный командами).^[19]

Дискретная томография [ править ]

Томография - это процесс восстановления форм из их поперечных сечений. В дискретной томографии , упрощенной версии проблемы, которая часто изучается, восстанавливаемая форма представляет собой полимино (подмножество квадратов в двумерной квадратной решетке ), а поперечные сечения предоставляют совокупную информацию о множествах квадратов в отдельных строках и столбцах решетки. Например, в популярных головоломках без грамматики , также известных как рисование числами или гридлерами, набор квадратов, которые необходимо определить, представляет собой темные пиксели в двоичном изображении., а входные данные, передаваемые решателю головоломки, говорят ему или ей, сколько последовательных блоков темных пикселей включить в каждую строку или столбец изображения и какой длины должен быть каждый из этих блоков. В других формах цифровой томографии о каждой строке или столбце дается еще меньше информации: только общее количество квадратов, а не количество и длина блоков квадратов. Эквивалентная версия проблемы состоит в том, что мы должны восстановить данную матрицу 0-1, учитывая только суммы значений в каждой строке и в каждом столбце матрицы.

Хотя существуют алгоритмы с полиномиальным временем для поиска матрицы, имеющей заданные суммы по строкам и столбцам, ^[20] решение может быть далеко не уникальным: любая подматрица в форме единичной матрицы 2 × 2 может быть дополнена, не влияя на правильность решения. . Поэтому исследователи искали ограничения на реконструируемую форму, которые можно использовать для ограничения пространства решений. Например, можно предположить, что форма связана; однако проверка наличия связанного решения является NP-полной. ^[21] Еще более ограниченная версия, которую легче решить, заключается в том, что форма ортогонально выпуклая.: один непрерывный блок квадратов в каждой строке и столбце. Усовершенствовав несколько предыдущих решений, Chrobak & Dürr (1999) показали, как эффективно реконструировать связанные ортогонально выпуклые формы с помощью 2-SAT. ^[22]Идея их решения состоит в том, чтобы угадать индексы строк, содержащих крайнюю левую и крайнюю правую ячейки фигуры, подлежащей восстановлению, а затем установить задачу 2-выполнимости, которая проверяет, существует ли форма, соответствующая этим предположениям и данным. суммы строк и столбцов. Они используют четыре переменные 2-выполнимости для каждого квадрата, который может быть частью данной формы, по одной, чтобы указать, принадлежит ли он каждой из четырех возможных «угловых областей» формы, и они используют ограничения, которые заставляют эти области не пересекаться, иметь желаемые формы, формировать общую форму с непрерывными строками и столбцами и иметь желаемые суммы строк и столбцов. Их алгоритм занимает время O ( m ³ n ), где m- меньшее из двух измерений входной формы, а n - большее из двух измерений. Позже тот же метод был распространен на ортогонально выпуклые формы, которые могли быть соединены только по диагонали, вместо того, чтобы требовать ортогональной связи. ^[23]

Батенбург и Костерс ( 2008 , 2009 ), являющиеся частью решателя для полных головоломок без грамматики , использовали 2-выполнимость для объединения информации, полученной из нескольких других эвристик . Получив частичное решение головоломки, они используют динамическое программирование в каждой строке или столбце, чтобы определить, заставляют ли ограничения этой строки или столбца какой-либо из его квадратов быть белым или черным, и могут ли любые два квадрата в одной строке или столбце быть связаны отношением импликации. Они также превращают нонограмму в проблему цифровой томографии, заменяя последовательность длин блоков в каждой строке и столбце ее суммой, и используют максимальный потокформулировка, чтобы определить, есть ли в этой задаче цифровой томографии, объединяющей все строки и столбцы, какие-либо квадраты, состояние которых может быть определено, или пары квадратов, которые могут быть связаны отношением импликации. Если одна из этих двух эвристик определяет значение одного из квадратов, оно включается в частичное решение, и те же вычисления повторяются. Однако, если обе эвристики не могут установить какие-либо квадраты, последствия, обнаруженные обеими из них, объединяются в проблему 2-выполнимости, и решатель 2-выполнимости используется для поиска квадратов, значение которых фиксируется задачей, после чего процедура снова повторил. Эта процедура может или не может успешно найти решение, но она гарантированно выполняется за полиномиальное время. Батенбург и Костерс сообщают, что, хотя большинство газетных головоломок не нуждаются в полной мощности,как эта процедура, так и более мощная, но более медленная процедура, которая сочетает в себе подход 2-выполнимости с ограниченным обратным отслеживаниемДаже Итаи и Шамир (1976) ^[5] значительно более эффективны, чем динамическое программирование и эвристика потока без 2-выполнимости, когда применяются к более сложным случайно сгенерированным нонограммам. ^[24]

Возможность переименования рожка [ править ]

Помимо 2-выполнимости, другой основной подкласс проблем выполнимости, который может быть решен за полиномиальное время, - это выполнимость по Хорну . В этом классе задач выполнимости входом снова является формула в конъюнктивной нормальной форме. В каждом предложении может быть сколь угодно много литералов, но не более одного положительного литерала. Льюис (1978) нашел обобщение этого класса, переименовываемую выполнимость Хорна , которое все еще может быть решено за полиномиальное время с помощью вспомогательного примера 2-выполнимости. Формула можно переименовать Hornкогда его можно преобразовать в форму Рога, заменив некоторые переменные их отрицаниями. Для этого Льюис устанавливает экземпляр 2-выполнимости с одной переменной для каждой переменной переименовываемого экземпляра Horn, где переменные 2-выполнимости указывают, следует ли отрицать соответствующие переименовываемые переменные Horn. Чтобы создать экземпляр Horn, никакие две переменные, которые появляются в одном и том же предложении переименованного экземпляра Horn, не должны появляться в этом предложении положительно; это ограничение на пару переменных является ограничением 2-выполнимости. Найдя удовлетворительное присвоение полученному экземпляру 2-выполнимости, Льюис показывает, как превратить любой переименовываемый экземпляр Horn в экземпляр Horn за полиномиальное время. ^[25]Разбив длинные предложения на несколько более мелких предложений и применив алгоритм 2-выполнимости с линейным временем, можно сократить это до линейного времени. ^[26]

Другие приложения [ править ]

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

Сложность и расширения [ править ]

NL-полнота [ править ]

Недетерминированная алгоритм для определения , является ли экземпляр 2-выполнимости является не выполним, используя только логарифмическое количество записываемой памяти, легко описать: просто выбрать (недетерминировано) переменную V и поиск (недетерминировано) для цепочки последствий , ведущей от V к его отрицанию, а затем обратно к ст . Если такая цепочка найдена, экземпляр не может быть выполнимым. По теореме Иммермана – Селепсеньи в недетерминированном лог -пространстве также можно проверить выполнимость выполнимого экземпляра 2-выполнимости.

2-выполнимость является NL-полным , ^[30] это означает , что это один из самых «трудных» или «наиболее выразительных» проблем в сложности класса NL задач , решаемой недетерминировано в логарифмическом пространстве. Полнота здесь означает, что детерминированная машина Тьюринга, использующая только логарифмическое пространство, может преобразовать любую другую проблему в NL в эквивалентную проблему 2-выполнимости. Аналогично аналогичным результатам для более известного класса сложности NP , это преобразование вместе с теоремой Иммермана – Селепсеньи позволяет представить любую проблему в NL в виде логики второго порядкаформула с одним экзистенциально определенным предикатом с предложениями, ограниченными длиной 2. Такие формулы известны как SO-Krom. ^[31] Точно так же импликативная нормальная форма может быть выражена в логике первого порядка с добавлением оператора для транзитивного замыкания . ^[31]

Набор всех решений [ править ]

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

Федер (1994) описывает алгоритм для эффективного перечисления всех решений данного экземпляра 2-выполнимости и для решения нескольких связанных проблем. ^[33] Также существуют алгоритмы для поиска двух удовлетворяющих назначений, которые имеют максимальное расстояние Хэмминга друг от друга. ^[34]

Подсчет количества удовлетворительных заданий [ править ]

# 2SAT - это проблема подсчета количества удовлетворяющих назначений данной формуле 2-CNF. Эта проблема подсчета является # P-полной , ^[35] что означает, что она не разрешима за полиномиальное время, если P = NP . Более того, нет полностью полиномиальной рандомизированной схемы аппроксимации для # 2SAT, если NP = RP, и это справедливо даже, когда ввод ограничен монотонными формулами 2-CNF, то есть формулами 2-CNF, в которых каждый литерал является положительным вхождением переменной . ^[36]

Самый быстрый из известных алгоритмов вычисления точного числа удовлетворяющих назначений формуле 2SAT выполняется во времени . ^{[37] [38] [39]}${\displaystyle O(1.2377^{n})}$

Случайные случаи 2-выполнимости [ править ]

Можно сформировать случай 2-выполнимости случайным образом для заданного числа n переменных и m предложений, выбирая каждое предложение равномерно случайным образом из множества всех возможных предложений с двумя переменными. Когда m мало по сравнению с n , такой пример, вероятно, будет удовлетворительным, но большие значения m имеют меньшую вероятность того, что он будет выполнимым. Точнее, если m / n фиксируется как константа α ≠ 1, вероятность выполнимости стремится к пределу, когда n стремится к бесконечности: если α <1, предел равен единице, а если α> 1, предел равен нулю. . Таким образом, в задаче наблюдается фазовый переходпри α = 1. ^[40]

Максимум-2-выполнимость [ править ]

В задаче максимальной-2-выполнимости ( MAX-2-SAT ) входными данными является формула в конъюнктивной нормальной форме с двумя литералами на каждое предложение, и задача состоит в том, чтобы определить максимальное количество предложений, которые могут быть одновременно удовлетворены назначением . Как и более общая проблема максимальной выполнимости , MAX-2-SAT NP-сложна . Доказательство - сокращение от 3SAT . ^[41]

Сформулируя MAX-2-SAT как задачу поиска разреза (то есть разделения вершин на два подмножества), максимизируя количество ребер, которые имеют одну конечную точку в первом подмножестве и одну конечную точку во втором, в графе связанного с графом импликации, и применяя методы полуопределенного программирования к этой задаче разрезания, можно найти за полиномиальное время приближенное решение, которое удовлетворяет по крайней мере 0,940… оптимальному количеству предложений. ^[42] сбалансирован экземпляр MAX 2-SAT является экземпляром MAX 2-SAT , где каждая переменная появляется положительно и отрицательно с равным весом. Для этой проблемы Острин улучшил коэффициент приближения до . ^[43]${\displaystyle \min \left\{(3-\cos \theta )^{-1}(2+(2/\pi )\theta )\,:\,\pi /2\leq \theta \leq \pi \right\}=0.943...}$

Если гипотеза об уникальных играх верна, то невозможно приблизить MAX 2-SAT, сбалансированное или нет, с константой приближения лучше, чем 0,943 ... за полиномиальное время. ^[44] При более слабом предположении, что P ≠ NP , проблема, как известно, не аппроксимируется только в пределах константы лучше, чем 21/22 = 0,95454 ... ^[45]

Различные авторы также исследовали экспоненциальные ограничения времени наихудшего случая для точного решения экземпляров MAX-2-SAT. ^[46]

Взвешенная-2-выполнимость [ править ]

В задаче взвешенной 2-выполнимости ( W2SAT ) входом является экземпляр -переменной 2SAT и целое число k , и проблема состоит в том, чтобы решить, существует ли удовлетворяющее присвоение, в котором истинно не более k переменных.${\displaystyle n}$

Задача W2SAT включает в себя как частный случай проблему покрытия вершин, состоящую в нахождении набора из k вершин, которые вместе касаются всех ребер данного неориентированного графа. Для любого данного случая проблемы покрытия вершин можно построить эквивалентную задачу W2SAT с переменной для каждой вершины графа. Каждое ребро uv графа может быть представлено предложением 2SAT u ∨ v, которое может быть удовлетворено только включением либо u, либо v в число истинных переменных решения. Тогда удовлетворяющие экземпляры результирующей формулы 2SAT кодируют решения проблемы вершинного покрытия, и существует удовлетворяющее присвоение с kистинные переменные тогда и только тогда, когда существует вершинное покрытие с k вершинами. Следовательно, как и вершинное покрытие, W2SAT является NP-полным .

Более того, в параметризованной сложности W2SAT обеспечивает естественную W [1] -полную задачу ^{[47], из} чего следует, что W2SAT не является управляемым с фиксированными параметрами, если это не выполняется для всех задач в W [1] . То есть маловероятно, что существует алгоритм для W2SAT, время работы которого имеет вид f ( k ) · n ^{O (1)} . Более того, W2SAT не может быть решен за время n ^{o ( k ),} если гипотеза экспоненциального времени не верна. ^[48]

Количественные логические формулы [ править ]

Помимо поиска первого полиномиального алгоритма 2-выполнимости, Кром (1967) также сформулировал проблему вычисления полностью количественно определенных булевых формул, в которых количественно определяемая формула является формулой 2-CNF. Проблема 2-выполнимости является частным случаем этой количественной проблемы 2-CNF, в которой все кванторы экзистенциальны . Кром также разработал эффективную процедуру принятия решения для этих формул. Aspvall, Plass и Tarjan (1979) показали, что эта проблема может быть решена за линейное время путем расширения их техники сильно связных компонентов и топологического упорядочения. ^{[2] [4]}

Многозначная логика [ править ]

Проблема 2-выполнимости также может быть задана для пропозициональной многозначной логики . Алгоритмы обычно не являются линейными, а для некоторых логик проблема даже NP-полная. См. Обзоры у Hähnle ( 2001 , 2003 ). ^[49]

Ссылки [ править ]