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

25
Проверка уникальных решений SAT

Рассмотрим следующую проблему: учитывая формулу CNF и присвоение, которое удовлетворяет этой формуле, есть ли другое удовлетворяющее назначение для этой формулы? В чем сложность этой проблемы? (Это наверняка есть в NP, но это также NP-hard?) Что если вам не дано назначение, и вы просто хотите...

24
Начиная SAT решающих работ

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

23
Что известно о сложности поиска минимальных каналов для SAT?

Что известно о сложности поиска минимальных схем, которые вычисляют SAT до длины ? nnn Более формально: какова сложность функции, которая, учитывая качестве входных данных, выводит минимальную схему C такую, что для любой формулы φ с | φ | ≤ n , C ( φ ) = S A T ( φ )...

22
Почему CNF используется для SAT, а не DNF?

Я не совсем понимаю, почему почти все решатели SAT используют CNF вместо DNF. Мне кажется, что решение SAT проще с использованием DNF. В конце концов, вам просто нужно просмотреть набор импликантов и проверить, содержит ли один из них и переменную, и ее отрицание. Для CNF не существует такой...

22
Существуют ли какие-либо сложные случаи использования 3-SAT, когда в предложениях можно использовать только те литералы, которые находятся «рядом» друг с другом?

Пусть переменные будут Икс1, х2, х3, , , ИксNИкс1,Икс2,Икс3,,,ИксNx_1 , x_2 , x_3 ... x_n . Расстояние между двумя переменными определяется как d( хa, хб) = | а - б |d(Иксa,Иксб)знак равно|a-б|d(x_a , x_b) = |a-b|, Расстояние между двумя литералами - это расстояние между соответствующими двумя...

22
Лучшая текущая космическая нижняя граница для SAT?

Исходя из предыдущего вопроса , Каковы наилучшие текущие нижние границы пространства для SAT? С нижней границей пробела здесь я имею в виду количество ячеек рабочей ленты, используемых машиной Тьюринга, которая использует двоичный алфавит рабочей ленты. Постоянный аддитивный член неизбежен,...

21
#SAT Solver скачать

Может ли кто-нибудь указать на один или несколько веб-сайтов, где можно загрузить работающую реализацию решателя #SAT? Меня интересуют те, кто возвращает точное количество решений, а не...

19
Существует ли недетерминированный линейный алгоритм времени для CNF-SAT?

Решение проблемы CNF-SAT можно описать следующим образом: Вход: булева формула в конъюнктивной нормальной форме.ϕφ\phi Вопрос: существует ли присвоение переменной, которая удовлетворяет ?ϕφ\phi Я рассматриваю несколько различных подходов к решению проблемы CNF-SAT с помощью недетерминированной...

19
Минимальные неудовлетворительные формулы 3-CNF

В настоящее время я заинтересован в получении (или построении) и изучении формул 3-CNF, которые являются неудовлетворительными и имеют минимальный размер. То есть они должны состоять из как можно меньшего числа предложений (предпочтительно m = 8) и как можно меньшего числа различных переменных (n =...

18
Разрешаемые экземпляры Max-Sat за полиномиальное время

Задача Max-Sat просит вас найти назначение формулы CNF, которое удовлетворяет как можно большему количеству предложений. Для более простой задачи SAT существует много известных частных случаев, которые могут быть решены за полиномиальное время, например, мы можем решить 2-SAT за полиномиальное...

18
Кратчайший эквивалент формулы CNF

Пусть F1F1F_1 - выполнимая формула CNF с nnn переменными и mmm предложениями. Пусть SF1SF1S_{F_1} - пространство решений F1F1F_1 . Рассмотрим проблему определения для данной F1F1F_1 другой формулы CNF F2F2F_2с тем же набором переменных, что и для F1F1F_1 , с SF2=SF1SF2=SF1S_{F_2} = S_{F_1} (то же...

18
Прямое снижение SAT до 3-SAT

Здесь цель состоит в том, чтобы свести произвольную задачу SAT к 3-SAT за полиномиальное время, используя наименьшее количество предложений и переменных. Мой вопрос мотивирован любопытством. Менее формально я хотел бы знать: «Каково« наиболее естественное »сокращение с SAT до 3-SAT?» Теперь...

18
Топологическое пространство, связанное с SAT: оно компактно?

Проблема удовлетворенности является, конечно, фундаментальной проблемой в теоретической CS. Я играл с одной версией проблемы с бесконечным количеством переменных. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Базовая настройка. Пусть непустое и, возможно, бесконечное множество...

18
Какова сложность подсчета случайных 2-SAT?

Была ли проделана какая-либо работа над тем, как сложность случайных экземпляров # 2-SAT зависит от плотности предложения? То есть: как изменяется сложность подсчета удовлетворяющих решений для случайно сгенерированного экземпляра 2-SAT , когда меняется плотность предложений? В частности, известны...

17
Открытое или интерактивное удовлетворение ограничений

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

17
Каковы # P-полные подсемейства # 2-SAT?

Укороченная версия. Первоначальное доказательство того, что # 2-SAT является #P -завершенным, фактически показывает, что экземпляры # 2-SAT являются монотонными (без учета отрицаний каких-либо переменных) и двудольными (график, образованный предложениями над Переменный является двудольным графом)...

16
Тавтологии / противоречия в среднем случае за пределами случайной модели k-CNF

Хорошо известно, что случайные формулы -CNF над n переменными с предложениями c n являются неудовлетворительными (т.е. являются противоречиями) с большой вероятностью для достаточно большой постоянной c . Таким образом, случайные формулы k- CNF (для достаточно больших c ) представляют собой...

16
Контекстно-зависимая грамматика для SAT?

Классическим результатом Куроды является то, что класс сложности NSPACE [ ]NNn (также известный как NLIN-SPACE) является именно классом CSL контекстно-зависимых языков . Задача выполнимости SAT находится в NSPACE [ ], так как предположение линейного размера для решения может быть проверено не более...