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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 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>
+

Версия 02:39, 26 декабря 2014

На каких входных данных алгоритм из этой темы, будет работать ?