Хорошо известно, что случайные формулы -CNF над n переменными с предложениями c n являются неудовлетворительными (т.е. являются противоречиями) с большой вероятностью для достаточно большой постоянной c . Таким образом, случайные формулы k- CNF (для достаточно больших c ) представляют собой...
SAT решатели дают мощный способ проверить правильность логической формулы с одним квантификатором. Например, чтобы проверить правильность , мы можем использовать SAT-решатель, чтобы определить, выполнимо ли . Чтобы проверить правильность , мы можем использовать SAT-решатель, чтобы определить,...
Если , то существует алгоритм пространства журнала, который решает версию решения 2-SAT.L = N LL=NL\mathsf{L = NL} Известно ли, что подразумевает наличие алгоритма логического пространства для получения удовлетворительного назначения , когда в качестве входных данных предоставляется...
Этот вопрос тесно связан с другим постом: Фазовые переходы в NP Трудные проблемы, но он несколько иной. В то время как этот вопрос касается сложности отдельных случаев сложных проблем NP, речь идет о ранжировании сложности тех же случаев. Существует много библиографии об эффекте, известном как...
Пусть - формула CNF с n переменными и m предложениями. Пусть t ∈ { 0 , 1 } n представляет присваивание переменной, а f φ ( t ) ∈ { 0 , … , m } подсчитывает количество предложений, удовлетворяемых присваиванием переменной φ . Затем определите Median-SAT как задачу вычисления медианного значения f φ...
Проблема #SAT является канонической # P-полной проблемой. Это скорее функциональная проблема, чем проблема решения. При булевой формуле в пропозициональной логике спрашивается, сколько удовлетворяющих заданий имеет. Каковы лучшие нижние границы на...
Критическое отношение предложений к переменным для случайных 3-SAT составляет более 3 и менее 6 и, как представляется, обычно описывается как «около 4,2» или «около 4,25». Mezard, Parisi и Zecchina доказывают (в физическом смысле), что критическое отношение составляет 4,256, тогда как первый и...
Я посмотрел в Интернете, но не смог найти «большой список» вариантов проблемы SAT. Помимо (общего) СИДЕЛ, к-СБ, MAX-КСАТ, Half-СБ, XOR-СБ, НАЗ-СБ какие еще варианты есть? (также будет очень полезно, если есть классы сложности (где это...
Были бы какие-нибудь серьезные последствия, если бы у SAT было самое большее субэкспоненциальное несогласованное доказательство или даже более сильно, у SAT были алгоритмы субэкспоненциального...
Формула Monotone-2CNF - это формула CNF, в которой каждое предложение состоит ровно из двух положительных литералов. Теперь у меня есть Монотонный-2CNF формула . Пусть S будет множеством удовлетворяющих заданий F. У меня также есть оракул O, который может дать следующую информацию:FFFSSSFFFOOO...
Напомним , что ширина резолюции опровержение RRR из формулы CNF FFF представляет максимальное число литералов в любом пункте , происходящих в RRR . Для каждого в 3-CNF wwwесть неудовлетворительные формулы FFF каждое опровержение разрешения FFF требует ширины не менее www . Мне нужен конкретный...
В Bundeswettberweb Infomatik 2010/2011 возникла интересная проблема: Для фиксированного найдите минимальное k и отображение φ : { ( i , j ) | i ≤ j ≤ n } → { 1 , … , k } , так что не существует тройки ( i , j ) , ( i + l , j ) , ( i + l , j + l ) с φ ( iNNnККkφ : { ( i , j ) | i ≤ j ≤ n } → { 1 , …...
Согласно этой статье , в которой обсуждается недетерминированное расширение гипотезы сильного экспоненциального времени (SETH), «[…] Уильямс недавно показал, что связанные гипотезы о сложности Мерлин-Артура k-TAUT являются ложными». Тем не менее, эта статья цитирует только личное общение. Как...
Мы знаем, что проблема подсчета количества удовлетворяющих назначений в данной общей булевой формуле (CNF-SAT), заданной формуле DNF или даже заданной формуле 2SAT является проблемой # P-полной . Теперь рассмотрит CNF-SAT без отрицательного литерала (не , всегда A ). Решить задачу очень легко...
Я начинаю исследовать возможность использования решателя SAT для решения интересующей меня проблемы оптимизации, и в настоящее время я ищу опрос, который будет содержать примеры «умных» преобразований в варианты SAT (то есть преобразований, которые приводят к в задаче разумного размера, так как...
Широко известно, что формулы CNF можно условно разделить на 2 широких класса: случайный и структурированный. Структурированные формулы CNF, в отличие от случайных формул CNF, демонстрируют некоторый порядок, демонстрируя паттерны, которые вряд ли могут произойти случайно. Тем не менее, можно найти...
Как можно показать, что определенное свойство не может быть выражено в 2-CNF (2-SAT)? Существуют ли игры, такие как игры в гальку? Похоже, что классическая игра с черной галькой и игра с черной и белой галькой для этого не подходят (они завершены PSPACE, согласно Hertel и Pitassi, SIAM J of...
Есть 4 различных ограничения, которые мы можем иметь при определении Random K-SAT. 1) Общее количество литералов в заданных предложениях в точности равно K или AT большинству K 2) Данный литерал может использоваться с заменой или без замены в одном и том же предложении (A или A или A) 3) Данная...
Я рассматриваю язык всех выполнимых логических формул высказываний, SAT (чтобы гарантировать, что у этого есть конечный алфавит, мы бы закодировали пропозициональные буквы некоторым подходящим способом [править: ответы указали, что ответ на вопрос, возможно, не является устойчивым при различные...
Уникальная SAT является хорошо известной проблемой: учитывая формулу CNF , верно ли, что F имеет ровно одну модель?FFFFFF Меня интересует проблема «точно -SAT»: учитывая формулу CNF F и целое число m > 1 , правда ли, что F имеет ровно m моделей?мmmFFFm > 1m>1m>1FFFmmm Обе проблемы выглядят...