Полиномиальный в среднем алгоритм для 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