Полиномиальный в среднем алгоритм для SAT/Задачи/ex-sat-dynp-bad-data — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 14 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Какие входные данные для алгоритма «alg-sat-dynp» заставят его работать экспоненциально долго?
 
Какие входные данные для алгоритма «alg-sat-dynp» заставят его работать экспоненциально долго?
  
[[Category:На проверку]]
+
 
 
<!--Вообще-то, решения уже есть-->
 
<!--Вообще-то, решения уже есть-->
  
===Стенина Мария, группа 974===
+
[[Категория:Решенные задачи]]
 
+
<latex>
+
Сложность этого алгоритма в худшем случае равна $O(m^2 n \max\limits_{k} |N_k|)$, где $N_k$ набор независимых множеств, содержащих $k$ скобок. Рассмотрим КНФ вида
+
$$
+
    x_1 \cap \ldots \cap x_m.
+
$$
+
Для такого входа $N_{m/2}$ имеет мощность порядка
+
$$
+
    |N_{m/2}| = C_m^{m/2} \sim \frac{\left(\frac{m}{e}\right)^m}{\left(\frac{m}{2e}\right)^{m/2} \left(\frac{m}{2e}\right)^{m/2}} = \frac{\left(\frac{m}{e}\right)^m}{\left(\frac{m}{2e}\right)^m} = \left( \frac{2me}{me} \right)^m = 2^m.
+
$$
+
Следовательно, на таком входе алгоритм будет работать экспоненциально долго.
+
 
+
</latex>
+

Версия 15:49, 20 мая 2020

Какие входные данные для алгоритма «alg-sat-dynp» заставят его работать экспоненциально долго?