Вопросы, касающиеся программ-решателей для задачи логической выполнимости.
Я использую решатель SAT для кодирования проблемы, и как часть экземпляра SAT, у меня есть логические переменные x1,x2,…,xnx1,x2,…,xnx_1,x_2,\dots,x_n где предполагается, что именно одна из них должна быть истинной, а остальные должны быть ложным (Я иногда видел, что это описывается как «горячая»...
Как я могу доказать, что преобразование из CNF в DNF является NP-Hard? Я не прошу ответа, просто несколько советов о том, как это
Если у меня возникла сложная проблема, один из стандартных подходов состоит в том, чтобы выразить его как экземпляр SAT и попробовать запустить на нем решатель SAT. Другой стандартный подход состоит в том, чтобы выразить это как проблему удовлетворения ограничений и попытаться использовать решатель...
После выпуска библиотеки AIGER для обработки и инвертирования графов где-то в 2006 году (я думаю), некоторые схемы SAT решатели были выпущены в 2006-2008 годах, и в нескольких гонках / соревнованиях SAT были треки AIG. Однако с тех пор кажется, что основное внимание было уделено либо SMT, либо...
Решатели SAT становятся все более и более эффективными в решении больших случаев и используются в качестве бэкэнда в различных контекстах. Каждый раз, когда кто-то хочет использовать их для решения проблемы в определенной области, он / она должен придумать специальную кодировку, которая не только...
Я пытаюсь решить проблему SAT переменных 25k пунктов 5k переменных. Так как он работал в течение часа (precosat), и я хотел бы потом решить более крупные, я ищу многоядерный SAT-Solver. Кажется, что есть много SAT-Solvers, я совершенно потерян. Кто-нибудь может указать мне лучший вариант для моего...
Современные SAT-решатели очень хороши в решении многих реальных примеров экземпляров SAT. Тем не менее, мы знаем, как генерировать сложные: например, использовать сокращение от факторинга до SAT и давать числа RSA в качестве входных данных. Возникает вопрос: что если я возьму простой пример...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Я читал в Википедии, что объединение - это процесс решения проблемы выполнимости. В то же время я знаю, что такие решатели называются «решателями SAT» или «решателями SMT». Так это разные имена для одного и того же? Если вы говорите, что они разные, пожалуйста, укажите на недостатки в моем лечении....
Я пытаюсь научить себя различным подходам к проверке программного обеспечения. Я прочитал несколько статей. Насколько я узнал, логика высказываний с темпоральным обычно использует проверку моделей с помощью решателей SAT (в текущих - реактивных системах), но как насчет логики первого порядка с...
На странице википедии здесь довольно хорошо описан алгоритм CDCL (и, похоже, фотографии были взяты из слайдов, созданных Шарадом Маликом в Принстоне). Тем не менее, при описании того, как откатить все, что он говорит, это «до соответствующей точки». MiniSAT также использует вариант алгоритма CDCL,...