Описание тега 2-satisfiability
Задача логической 2-выполнимости спрашивает, существует ли решение для данного набора парных ограничений на булевы переменные. 2SAT, как его обычно называют, разрешима за полиномиальное время.
2
ответа
2-SATisfiabilty проблемных тестовых случаев
Я написал SAT решатель для задачи 2-удовлетворяемости, кто-то, пожалуйста, предоставьте мне контрольный пример, скажем, 10000 литералов, который имеет только одно выполнимое назначение, т.е. только одно решение The format can be:(for 3 literals) 2 /…
04 ноя '09 в 09:16
2
ответа
Как получить значения 2-Sat
Всякий раз, когда я ищу алгоритм для 2-Sat, я возвращаюсь алгоритм для формы решения проблемы: существует ли допустимый набор значений, который удовлетворяет всем пунктам. Однако это не позволяет мне легко найти набор удовлетворяющих булевых значени…
22 фев '10 в 16:50
1
ответ
2-Удовлетворенность и Сильно связанные компоненты
Я знаю, что, применяя сильно связанные компоненты в орграфе, мы можем проверить булеву выполнимость 2-SAT, если задача разрешима за полиномиальное время. Let's assume the problem is satisfiable. The question: is there a general algorithm to calculat…
03 ноя '13 в 16:36
1
ответ
Преобразование не всех равных 2-Sat Pr0blem в эквивалентную 2-SAT pr0blem
Я просматриваю предыдущие экзаменационные работы и сталкиваюсь с вопросом, который меня смутил. Вопрос: Преобразовать задачу Не-все-равные 2-SAT, заданную в пунктах {x1, x2}, {x2, x3}, {x3, x4}, {x4, x5}, {x5, x1} к эквивалентной проблеме 2-SAT. (По…
04 май '16 в 14:04
1
ответ
2 выполнимости сильно связанного компонента топологического упорядочения
Я решаю проблему с двумя выполнимостями с SCC, и у меня есть вопрос о топологической сортировке. Алгоритм, на котором я это основываю, заключается в обработке SCC в обратном топологическом порядке, что хорошо, когда все они подключены. Мой алгоритм …
02 апр '17 в 01:56
1
ответ
Могу ли я уменьшить использование памяти в этом коде C++?
#include <bits/stdc++.h> using namespace std; int n; vector<bool> used; vector<int> order, comp; void dfs1 (int v,const vector<vector<int>>& g) { used[v] = true; for (size_t i=0; i<g[v].size(); ++i) { int to = g[…
18 ноя '18 в 09:18
2
ответа
Решение 2Sat CNF формы с помощью грубой силы
В настоящее время я изучаю задачу 2SAT для экзамена, и я не совсем понимаю, как проверить, существует ли решение с использованием грубой силы. Я знаю, что это кажется немного странным, но я понимаю, как реализовать граф импликации немного лучше, но …
08 фев '13 в 18:40
1
ответ
2-проблема удовлетворенности - существует ли уникальное правдивое назначение или нет
У меня есть проблема, которая является расширением проблемы 2-SAT. В стандартной задаче 2-SAT мы можем найти любое из назначений истинности, которое зависит от порядка вершин, которые мы выбираем. Я хочу проверить, существует ли одно и только одно п…
03 ноя '09 в 03:07
1
ответ
Полиномиальный алгоритм для алгоритма, связанного с 2-SAT
Я прочитал много алгоритмов для нахождения задачи 2-SAT, т.е. данное выражение выполнимо или нет, которое может быть решено за полиномиальное время. пример ( алгоритм).Для процедуры Крома( Википедия) я строю граф, из которого я могу легко проверить …
04 ноя '15 в 22:44
1
ответ
Кто-нибудь видел реализацию 2-Sat
Я искал некоторое время, но я просто не могу найти какую-либо реализацию алгоритма 2-Sat. Я работаю в C++ с библиотекой boost (которая имеет сильно связанный компонентный модуль), и мне нужно некоторое руководство, чтобы создать эффективную 2-Sat пр…
14 ноя '09 в 08:10
1
ответ
Как постоянные входные данные влияют на постановку задачи SAT?
Допустим, у меня есть схема черного ящика с N входами и 1 выходом. Я хочу зафиксировать значение M входов и найти значение остальных входов (NM), для которых схема является удовлетворительной. Если я вручную исправлю вводы M в RTL Verilog и преобраз…
21 сен '18 в 18:38
1
ответ
Назначение графа импликации
Граф импликации - это ориентированный граф, в котором каждому узлу присваивается значение true или false, а любое ребро u -> v подразумевает, что if u is true then v is true, Я знаю прямолинейно O(n^2) алгоритм, чтобы найти назначение в графе общ…
20 сен '14 в 19:34
2
ответа
Вопросы реализации в проблеме 2-удовлетворенности
Я хочу реализовать задачу 2-SAT для 100000 литералов. Таким образом, было бы 200000 вершин. Так что я застрял на наличие массива всех достижимых вершин из каждой вершины, сложность пространства O(200000^2) что невозможно, поэтому, пожалуйста, предло…
03 ноя '09 в 03:59
1
ответ
Как решить экземпляр 2-SAT с 60 логическими переменными и 99 предложениями, используя Z3Py
Я использую следующий код: X = BoolVector('x', 60) M = [[21, 34],[-49, -12],[7, 18], [-5, -1],[28, 17], [3, 55],[36, 33], [-6, -50],[44, -41], [-55, 3],[14, -54],[-30, 13], [-13, 60],[54, -16],[-48, 41], [3, 6],[49, -48],[34, -4], [14, -46],[58, -20…
12 июл '13 в 19:22
1
ответ
Как именно макс 2 сб сокращается до 3 сб?
Я читал эту статью, которая пытается объяснить, как проблема с max 2 sat по сути является проблемой 3 sat и сложна для NP. Однако, если вы видите статью, я не могу понять, почему после ci выполнено 7 из 10 пунктов, а если оно не выполнено, 6 из 10 п…
30 янв '16 в 10:41
1
ответ
Я понимаю, что 2 SAT могут быть решены за полиномиальное время, обнаруживая сильно связанные компоненты. Что делать с 3SAT?
В случае 3SAT вместо того, чтобы получить 2 значения для одного предложения, мы получили бы 12(3C2*2*2) возможно. И которые сформируют график 12-метровых ребер, когда m - это количество предложений в 3 CNF, и мы все еще можем найти Сильно Связанные …
11 ноя '18 в 13:07
0
ответов
Как найти действительный набор литералов из 2-SAT
это проблема 2-выполнимости. Я могу определить, удовлетворяются ли условия 2, используя алгоритм Косараю. Например, для первого теста, +1 +3 +2 -1 +2 -3 -1 -2 Я получил этот график импликации. Здесь я представил -1 до -3, используя узел 4-6. Итак, …
08 сен '17 в 08:31
1
ответ
2-SAT значения переменной
Задача 2-SAT, поиск значения для переменных Я использую это решение для нахождения удовлетворенности для данной формулы. (проверяя ГТК). Есть ли эффективный способ (эффективный означает не хуже, чем полиномиальное время в моем случае), как найти зна…
21 апр '19 в 14:42
1
ответ
Генерация решений на 2-SAT от существующего
Алгоритм полиномиального времени 2-SAT с участием SCC сообщает нам, существует ли решение или нет, а также помогает нам в создании решения проблемы. Но решений может быть несколько. Я хотел знать, можно ли эффективно генерировать другие решения, исп…
13 ноя '20 в 11:43
0
ответов
Показать, что DOUBLE-SAT находится в NP [закрыто]
Пусть DOUBLE-SAT = {⟨φ⟩ | φ имеет по крайней мере два удовлетворяющих назначения}. Покажите, что DOUBLE-SAT находится в NP, указав для него верификатор с полиномиальным временем и объяснив, почему верификатор работает за полиномиальное время. Пожалу…
12 май '21 в 19:18