Полиномиальный в среднем алгоритм для SAT/Задачи/ex-sat-dynp-good-data — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Larisa (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
На каких входных данных алгоритм из этой темы, будет работать <m>O(m)</m>? | На каких входных данных алгоритм из этой темы, будет работать <m>O(m)</m>? | ||
− | [[Category: | + | [[Category:На проверку]] |
− | < | + | |
+ | <latex> | ||
+ | Рассмотрим КНФ состоящий из одной переменной $x_1$, где в каждой скобке $x_1$ входит вместе с отрицанием. | ||
+ | Тогда количество шагов алгоритма = 1. | ||
+ | Для каждой скобки $C_j$, если $x_1$ из $C_j$, то отрицание $x_1$ тоже из $C_j$. Тогда $P_j = 0$ (вероятность невыполнения j-ой скобки). | ||
+ | Следовательно алгоритм не будет тратить время на подсчет $P_j$ и будет работать за время O(m), где m - это количество скобок. | ||
+ | |||
+ | </latex> |
Версия 16:09, 12 декабря 2014
На каких входных данных алгоритм из этой темы, будет работать ?