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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 12 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
На каких входных данных алгоритм из этой темы, будет работать <m>O(m)</m>?  
 
На каких входных данных алгоритм из этой темы, будет работать <m>O(m)</m>?  
  
−
[[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>
+
[[Категория:Решенные задачи]]

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

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

Источник — «https://discopal.ispras.ru/index.php?title=Полиномиальный_в_среднем_алгоритм_для_SAT/Задачи/ex-sat-dynp-good-data&oldid=11110»