Полиномиальный в среднем алгоритм для SAT/Задачи/ex-sat-dynp-bad-data — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
Строка 1: | Строка 1: | ||
Какие входные данные для алгоритма «alg-sat-dynp» заставят его работать экспоненциально долго? | Какие входные данные для алгоритма «alg-sat-dynp» заставят его работать экспоненциально долго? | ||
− | [[Category: | + | [[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> |
Версия 18:35, 9 ноября 2014
Какие входные данные для алгоритма «alg-sat-dynp» заставят его работать экспоненциально долго?
Стенина Мария, группа 974