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

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

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

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

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

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

Граф последствий для примера 2-выполнимости, показанного в этом разделе.

Проблема 2-выполнимости может быть описана с помощью логического выражения специальной ограниченной формы. Это соединение (логическое значение и операция) предложений , где каждое предложение представляет собой дизъюнкцию (логическое значение или операцию) двух переменных или отрицательных переменных. Переменные или их отрицания, входящие в эту формулу, называются литералами . Например, следующая формула представлена ​​в конъюнктивной нормальной форме с семью переменными, одиннадцатью предложениями и 22 литералами: $${\begin{aligned}&(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 {}\\&(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 {}\\&(x_{3}\lor x_{6})\land (x_{4}\lor x_{6})\land (x_{5}\lor x_{6}).\end{aligned}}$$

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

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

Каждое предложение в формуле 2-CNF логически эквивалентно импликации одной переменной или отрицательной переменной к другой. Например, второе предложение в примере может быть записано любым из трех эквивалентных способов: $$(x_{0}\lor \lnot x_{3})\;\equiv \;(\lnot x_{0}\Rightarrow \lnot x_{3})\;\equiv \;(x_{3}\Rightarrow x_{0}).$$Из-за этой эквивалентности между этими различными типами операций экземпляр 2-выполнимости также может быть записан в импликативной нормальной форме , в которой мы заменяем каждое предложение или в конъюнктивной нормальной форме двумя импликациями, которым он эквивалентен.

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

Алгоритмы

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

Разрешение и транзитивное замыкание

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

Предположим, что экземпляр 2-выполнимости содержит два предложения, оба из которых используют одну и ту же переменную x , но x отрицается в одном предложении, а не в другом. Затем два предложения могут быть объединены в третье предложение, имеющее два других литерала в двух предложениях; это третье положение также должно соблюдаться всякий раз, когда соблюдаются оба первых двух пункта. Это называется разрешением . Например, мы можем объединить предложения $(a\lor b)$ и $(\lnot b\lor \lnot c)$ таким образом составить предложение $(a\lor \lnot c)$. С точки зрения импликативной формы формулы 2-КНФ это правило сводится к нахождению двух импликаций. $\lnot a\Rightarrow b$ и $b\Rightarrow \lnot c$и выводя по транзитивности третью импликацию $\lnot a\Rightarrow \lnot c$.

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

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

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

Ограниченный возврат

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

Форман и Вагнер (1991) используют 2-выполнимость как часть аппроксимационного алгоритма для задачи поиска квадратных меток максимально возможного размера для заданного набора точек с ограничением, что каждая метка имеет один из своих углов в точке, которая оно маркирует. Чтобы найти метку заданного размера, они исключают квадраты, которые в случае удвоения перекрывали бы другую точку, и исключают точки, которые можно пометить таким образом, чтобы они не могли перекрываться с меткой другой точки. Они показывают, что эти правила исключения приводят к тому, что оставшиеся точки имеют только два возможных размещения меток на точку, что позволяет найти допустимое размещение метки (если таковое существует) в качестве решения для случая 2-выполнимости. Путем поиска наибольшего размера метки, который приводит к разрешимому экземпляру 2-выполнимости, они находят допустимое размещение меток, метки которых как минимум вдвое меньше оптимального решения. То есть коэффициент аппроксимации их алгоритма не более двух. Аналогично, если каждая метка имеет прямоугольную форму и должна быть размещена таким образом, чтобы точка, которую она метит, находилась где-то вдоль ее нижнего края, то, используя 2-выполнимость, найдите наибольший размер метки, для которого существует решение, в котором каждая метка имеет точка в нижнем углу приводит к коэффициенту аппроксимации не более двух.

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

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

Кластеризация данных

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

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

Планирование

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

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

Дискретная томография

Пример головоломки-нонограммы.

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

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

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

Возможность переименовывания Horn

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

Другие приложения

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

Сложность и расширения

NL-полнота

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

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

Набор всех решений

Медианный график , представляющий все решения примера 2-выполнимости, график последствий которого показан выше.

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

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

Подсчет количества удовлетворяющих заданий

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

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

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

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

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

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

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

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

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

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

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

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

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

Количественные логические формулы

Помимо нахождения первого алгоритма с полиномиальным временем для 2-выполнимости, Кром (1967) также сформулировал проблему вычисления полностью квантифицированных булевых формул, в которых квантифицированная формула является формулой 2-КНФ. Проблема 2-выполнимости является частным случаем этой квантифицированной проблемы 2-КНФ, в которой все кванторы являются экзистенциальными . Кром также разработал эффективную процедуру принятия решений для этих формул. Аспвалл, Пласс и Тарьян (1979) показали, что ее можно решить за линейное время путем расширения их техники сильно связанных компонентов и топологического упорядочения.

Многозначная логика

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