Сколько здесь тавтологий?

Учитывая , сколько из -DNF с переменными и предложениями являются тавтологическими? (или сколько CNF неудовлетворительно?)к н м $m, n, k$$k$$n$$m$$k$

Ответ зависит от $k$ , $m$ и $n$ . Точные значения обычно не известны, но существует «пороговое» явление, при котором для большинства настроек $k$ , $m$ , $n$ либо почти все экземпляры $k$ -SAT являются удовлетворительными, либо почти все экземпляры являются неудовлетворительными. Например, когда $k=3$ , эмпирически наблюдалось, что когда $m < 4.27 n$ , все, кроме $o(1)$ доли экземпляров 3-SAT являются выполнимыми, а когда $m > 4.27n$ , все, кроме a фракция является неудовлетворительной. (Есть также строгие доказательства известных границ.)$o(1)$

Одной из отправных точек является «Асимптотический порядок порога k-SAT» .

Амин Кожа-Оглан также проделал большую работу по решению этих проблем порога удовлетворяемости .

Это расширенный комментарий, дополняющий ответ Райана, в котором рассматриваются пороговые значения, при которых количество предложений становится достаточно большим, чтобы экземпляр почти наверняка был неудовлетворительным. Можно также вычислить гораздо больше пороговых значений , где количество статей сил невыполнимости , когда оно превышает функцию .$n$

Обратите внимание, что необходимо решить некоторые технические проблемы. Если повторные предложения подсчитываются в , то m можно сделать настолько большим, насколько это необходимо, без изменения n . Это разрушило бы большинство отношений между m и n . Итак, предположим, что m - это число различных предложений. Нам нужно определиться с другой деталью, кодируются ли экземпляры так, чтобы порядок литералов в предложении или порядок предложений в экземпляре имели значение. Предположим, что это не важно, поэтому два экземпляра считаются эквивалентными, если они содержат одинаковые предложения, и два предложения эквивалентны, если они содержат одинаковые литералы. С этими допущениями мы можем теперь связать число различных предложений, которые могут быть выражены с$m$$m$$n$$m$$n$$m$ переменных. Каждое предложение может иметь каждую переменную, встречающуюся положительно или отрицательно, или не иметь ее вообще, и тогда m ≤ 3 n .$n$$m\le 3^n$

Сначала рассмотрим SAT без ограничения на . Какое наибольшее m такое, что экземпляр является выполнимым? Без ограничения общности можно предположить, что присваивание всех нулей является решением. Затем существует 3 n - 2 n различных предложений, соответствующих этому решению, каждое из которых содержит хотя бы один отрицательный литерал. Следовательно, m ≤ 3 n - 2 n для любого выполнимого случая. Экземпляр, состоящий из всех предложений, каждое из которых содержит хотя бы один отрицательный литерал, имеет столько предложений и удовлетворяется присваиванием «все ноль». Кроме того, по принципу голубиных яиц любой случай с по крайней мере 3 $k$$m$$3^n-2^n$$m\le 3^n-2^n$ пунктов неудовлетворительно.$3^n-2^n+1$

Это дает различных подмножеств таких предложений, каждое из которых представляет отдельный экземпляр, который удовлетворяется некоторым назначением. Для сравнения, общее количество разных экземпляров составляет 2 3 n .$2^{3^n-2^n}$$2^{3^n}$

Теперь изменив вышеприведенное для случаев, в которых каждое предложение имеет не более литералов, существует ∑ k i = 0 ($k$различных таких положений, иΣ K я = 0 ($\sum_{i=0}^k \binom{n}{i}2^i$$\sum_{i=0}^k \binom{n}{i}$$m\le \sum_{i=0}^k \binom{n}{i}(2^i - 1)$$m$$2^{\sum_{i=0}^k \binom{n}{i}(2^i - 1)}$$2^{\sum_{i=0}^k \binom{n}{i}2^i}$ $k$