Давнее
https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/balint/SAT2012.pdf
Решил освежить.
Вот цитата:
Scaling behavior with N: The survey propagation algorithm scales linearly with N on formulas generated near the threshold ratio.
Я думал, что хороших алгоритмов решения случайных k-SAT задач в области фазового перехода нет. Даже "доказательство работы" придумал, основываясь на этой задаче.
А оно вона, как! Решают, без проблем.
Век живи, век учись, дураком помрёшь. ;)
Решил освежить.
Вот цитата:
Scaling behavior with N: The survey propagation algorithm scales linearly with N on formulas generated near the threshold ratio.
Я думал, что хороших алгоритмов решения случайных k-SAT задач в области фазового перехода нет. Даже "доказательство работы" придумал, основываясь на этой задаче.
А оно вона, как! Решают, без проблем.
Век живи, век учись, дураком помрёшь. ;)