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

Каковы лучшие нижние границы тока для времени и глубины цепи для

В другой ветке Джо Фитцсимонс спросил о «лучших текущих нижних границах на 3SAT». Я хотел бы пойти по другому пути: каковы лучшие текущие верхние границы на 3SAT? Другими словами, какова временная сложность наиболее эффективного SAT-решателя? В частности, возможно ли найти субэкспоненциальный (но...

Какие теоретические объяснения есть для практического успеха решателей SAT, и может ли кто-нибудь дать обзор и объяснение в стиле «википедии», связав их всех вместе? По аналогии, сглаженный анализ ( версия arXiv ) для симплексного алгоритма делает большую работу, объясняя, почему он так хорошо...

В этом вопросе формула 3CNF означает формулу CNF, в которой каждое предложение включает ровно три различные переменные. Для константы 0 < s <1 Gap-3SAT s является следующей проблемой обещания: GAP-3sat сек экземпляра : а 3CNF формула φ. Да-обещание : φ выполнимо. Нет-обещание : Нет истину...

Решение, если количественная логическая формула, такая как ∀ х1∃ х2∀ х3⋯ ∃ хNφ ( х1, х2, … , ХN) ,∀Икс1∃Икс2∀Икс3⋯∃ИксNφ(Икс1,Икс2,...,ИксN),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), всегда оценивается как истина - это классическая PSPACE-полная проблема....

Кто-нибудь осмелится попытаться выяснить, какова связь между этими областями обучения или, возможно, даже дать более конкретный ответ на уровне проблем? Например, включает в себя некоторые общепринятые формулировки. Если я правильно понял, когда вы переходите от SAT к SMT, вы в основном входите в...

Определим - S U B E X P как класс языков L , для которого существует язык L ′ ∈ ∩ ε > 0 T I M E ( 2 n ε ) и для бесконечного множества n , L и L ′ согласны на всех экземплярах длины n . (То есть это класс языков, которые могут быть «решены бесконечно часто, в субэкспоненциальном...

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

Классические алгоритмы могут решать 3-SAT за времени (рандомизированный) или времени (детерминированный). (Ссылка: лучшие верхние границы по SAT )1,3071N1,3071N1.3071^n1,3303N1,3303N1.3303^n Для сравнения, используя алгоритм Гровера на квантовом компьютере, можно было бы найти и найти решение в ,...

Рассмотрим задачу 3-SAT для n переменных. Количество возможных отдельных предложений: C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C=2n×2(n−1)×2(n−2)/3!=4n(n−1)(n−2)/3.C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text. Количество проблемных экземпляров есть число всех подмножеств множества...

Сегодня в блоге Скотта Ааронсона приведен список интересных открытых задач / задач по сложности. Один из них привлек мое внимание: Создайте публичную библиотеку из 3SAT-экземпляров, используя как можно меньше переменных и предложений, что может привести к значительным последствиям в случае ее...

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

Что такое «легкие регионы» для удовлетворения? Другими словами, достаточные условия для того, чтобы некоторые SAT-решатели могли найти удовлетворяющее назначение, предполагая, что оно существует. Одним из примеров является то, что, когда каждое предложение совместно использует переменные с...

Читая статью «Пора ли объявить победу в подсчете сложностей?» в блоге «Потерянное письмо Годеля и P = NP» они упомянули дихотомию для CSP. После некоторой ссылки, поиска в Google и википедирования, я наткнулся на теорему Ладнера : Теорема Ладнера: если , то в N P ∖ P существуют проблемы , которые...

Можно ли перевести булеву формулу B в эквивалентное соединение выражений Хорна? Статья в Википедии о HornSAT, похоже, подразумевает, что это так, но я не смог найти какую-либо ссылку. Обратите внимание, что я имею в виду не «за полиномиальное время», а скорее...

Некоторые NP-сложные задачи, которые являются экспоненциальными на общих графах, являются субэкспоненциальными на плоских графах, потому что ширина дерева не более и они экспоненциальны в ширине дерева.4.9 | В( G ) |------√4.9|V(G)|4.9 \sqrt{|V(G)|} В основном меня интересует, существуют ли...

Меня интересует критическая плотность 3-удовлетворяемости (3-SAT) . Предполагается, что такой α существует: если количество случайно сгенерированных 3-SAT-предложений равно ( α + ϵ ) n или более, они почти наверняка неудовлетворительны. (Здесь ϵ - любая малая постоянная, а n - число переменных.)...

Для формулы 3CNF пусть будет максимальное число удовлетворенных положений в любом присвоении . Известно, что Max-3SAT трудно аппроксимировать (при условии P ≠ NP), то есть не существует алгоритма множителя, вход которого является формулой 3CNF , а выход которого равен числу , так что находится в...

Хорошо известной характеристикой экземпляров -SAT является отношение числа предложений m к числу переменных n , т. Е. Частное ρ = m / n . Для каждого k существует пороговое значение α st \ для ρ ≪ α , большинство случаев выполнимо, а для ρ ≫ α большинство случаев неудовлетворительно. Было проведено...

SAT решатели очень важны при алгебраических атаках , например, walksat и minisat . Тем не менее, при решении проблем с эталонными тестами, имеющихся здесь, существует огромная разница в производительности - Walksat намного быстрее, чем minisat для этих задач. Почему это? Эта реализация walksat,...