Вопросы с тегом «satisfiability»

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

Я использую решатель SAT для кодирования проблемы, и как часть экземпляра SAT, у меня есть логические переменные x1,x2,…,xnx1,x2,…,xnx_1,x_2,\dots,x_n где предполагается, что именно одна из них должна быть истинной, а остальные должны быть ложным (Я иногда видел, что это описывается как «горячая»...

Пусть - булева формула, состоящая из обычных операторов AND, OR, NOT и некоторых переменных. Я хотел бы, чтобы подсчитать число удовлетворяющих назначений для B . То есть я хочу найти количество различных назначений значений истинности для переменных для которых принимает истинное значение....

То, что я хочу сделать, это превратить мою математическую задачу в булеву проблему удовлетворенности (SAT), а затем решить ее с помощью SAT Solver. Интересно, знает ли кто-нибудь руководство, руководство или что-нибудь, что поможет мне преобразовать мою проблему в экземпляр SAT. Кроме того, я хочу...

WalkSAT и GSAT являются хорошо известными и простыми алгоритмами локального поиска для решения проблемы булевой выполнимости. Псевдокод для алгоритма GSAT скопирован с вопроса Реализация алгоритма GSAT - Как выбрать, какой литерал переворачивать? и представлены ниже. procedure...

Недавно я нашел в статье [1] специальную симметричную версию SAT, называемую 2/2/4-SAT . Но есть много завершенных вариантов, например: MONOTONE NAE-3SAT , MONOTONE 1-IN-3-SATNPNP\text{NP} , ... Есть и другие варианты: - SAT , Planar-NAE- SAT222SATSAT\text{SAT}SATSAT\text{SAT} , ... Существуют ли...

Как я могу доказать, что преобразование из CNF в DNF является NP-Hard? Я не прошу ответа, просто несколько советов о том, как это

Алгоритм GSAT по большей части прост: вы получаете формулу в соединительной нормальной форме и переворачиваете литералы предложений до тех пор, пока не найдете решение, удовлетворяющее формуле, или не достигнете предела max_tries / max_flips и не найдете решения. Я реализую следующий алгоритм:...

У меня NP-полное решение проблемы. Учитывая пример проблемы, я хотел бы разработать алгоритм, который выводит ДА, если проблема выполнима, и НЕТ, в противном случае. (Конечно, если алгоритм не является оптимальным, он будет делать ошибки.) Я не могу найти никаких приближенных алгоритмов для таких...

После выпуска библиотеки AIGER для обработки и инвертирования графов где-то в 2006 году (я думаю), некоторые схемы SAT решатели были выпущены в 2006-2008 годах, и в нескольких гонках / соревнованиях SAT были треки AIG. Однако с тех пор кажется, что основное внимание было уделено либо SMT, либо...

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

Мы говорим, что язык является плотным, если существует такой многочлен , что для всехДругими словами, для любой заданной длины существует только многочлен много слов длины , которых нет вJ⊆ Е*J⊆Σ*J \subseteq \Sigma^{*}| J c ∩ Σ n | ≤ р ( п ) п ∈ N . п п J .ппp| Jс∩ ЕN| ≤p(n)|Jс∩ΣN|≤п(N) |J^c \cap...

Я пытаюсь обернуть голову вокруг доказательства полноты NP, которое, кажется, вращается вокруг SAT / 3CNF-SAT. Возможно, это поздний час, но я боюсь, что не могу придумать формулу 3CNF, которая не может быть удовлетворена (возможно, я упускаю что-то очевидное). Можете ли вы привести пример такой...

Предположим, нам даны два числа и и мы хотим найти для .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Наивный алгоритм просто проверяет все возможные пары; например, в ruby ​​у нас будет: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if (i ^ j > max) max...

Итак, как известно, проблема решения ILP 0-1 является NP-полной. Показать его в NP легко, а оригинальное сокращение было от SAT; с тех пор было доказано, что многие другие проблемы NP-Complete имеют составы ILP (которые функционируют как сокращение от этих проблем до ILP), потому что ILP очень...

Планар 3SAT является NP-полным. Планарный экземпляр 3SAT - это экземпляр 3SAT, для которого график, построенный с использованием следующих правил, является плоским: добавить вершину для каждого и ¯ х яxixix_ixi¯xi¯\bar{x_i} добавить вершину для каждого предложения CjCjC_j добавить ребро для каждого...

Я уверен, что кто-то думал об этом раньше или сразу же отклонил это, но почему теория дихотомии Шефера наряду с теоремой Махани о разреженных множествах не подразумевает P = NP? Вот мои рассуждения: создайте язык который равен SAT, пересекаемому бесконечным разрешимым разреженным множеством. Тогда...

Хорошо известная проблема SAT определена здесь для справки. Проблема DOUBLE-SAT определяется как DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least...

Какова сложность MIN-2-XOR-СБMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} и MAX-2-XOR-СБMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? Они в П? Они NP-хард? Чтобы формализовать это более точно, пусть Φ ( x ) = ∧NяСя,Φ(x)=∧inCi,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, где х =( х1, … , Хм)x=(x1,…,xm)\mathbf{x}...

Я пытаюсь решить эту проблему, и я действительно борюсь. Монотонная булева формула представляет собой формулу в логике высказываний , где все литералы являются положительными. Например, (x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)(x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor...