Предположим, что мы рассматриваем 3-SAT с переменными и c предложениями. Я исследую метод, который, по-видимому, использует O ( v 2 + log c ) время / пространство для решения любой задачи SAT, соответствующей данному описанию, с точностью до ошибки, которую можно скорректировать до произвольной...
Стандартная проблема 1-в-3 SAT (или XSAT или X3SAT): Экземпляр : формула CNF с каждым предложением, содержащим ровно 3 литерала. Вопрос : есть ли удовлетворительная установка присваивания, точно равная 1 литералу на предложение, верно? Проблема является NP-полной и остается сложной, даже если...
Интересно, есть ли у них какие-либо подходы, формулирующие проблему маршрутизации транспортного средства с временными окнами ( VRPTW ) (как проблему решения) в качестве экземпляра SAT / SMT? (альтернатива: TSP) Например: «Есть ли правильное решение для посещения всех клиентов в пределах их...
Рассмотрим классическую # P-полную задачу # 3SAT, т. Е. Посчитаем количество оценок, чтобы сделать 3CNF с переменными выполнимыми. Меня интересует аддитивная аппроксимируемость. Ясно, что существует тривиальный алгоритм для достижения -ошибки, но если , возможно ли иметь эффективный алгоритм...
Я хотел бы знать, куда я могу обратиться за хорошим, мягким введением в k-SAT (это может быть для математиков, которые могут не иметь хорошего компьютерного фона). Я также хотел бы знать статьи, которые, возможно, опрашивают или объясняют текущие методы, используемые для решения k-SAT. Наконец,...
Рассмотрим формулу Monotone 3CNF, имеющую оба следующих дополнительных ограничения: Каждая переменная появляется в точности 222 статьи. Учитывая любой 222 пункты, они разделяют не более 111 переменная. Я хотел бы знать, насколько сложно рассчитывать удовлетворяющие задания такой формулы. Обновление...
Решатели SMT, такие как Z3 или Boolector, используют сложный набор эвристик для решения проблем. Однако это также затрудняет прогнозирование производительности такого решателя для данной проблемы. Мой вопрос таков: Вопрос Есть ли способ понять или получить представление о производительности...