Очередная попытка доказать P=NP
Позволю себе процитировать запись SAT07/crafted/Medium/contest05/jarvisalo/mod2-3cage-unsat-9-12.sat05-2587.reshuffled-07.cnf
Also, while running your program on uuf100-0345.cnf benchmark from SATLIB, I noticed that displayed value of nextTierIndex sometimes decreases. For example, 37-38-39-40-41-42-43-44, then 43-44-45, 42-43-44-45-46, again 42-43-44-45-46-47-48, then 47-48-49, 47-48-49-50 and so on in groups consisting of 3-4 consecutive values. Since I didn’t understand the algorithm, it looks suspiciously like backtracking search for me. It can be helpful if you explain why it isn’t exponential.
Also, while running your program on uuf100-0345.cnf benchmark from SATLIB, I noticed that displayed value of nextTierIndex sometimes decreases. For example, 37-38-39-40-41-42-43-44, then 43-44-45, 42-43-44-45-46, again 42-43-44-45-46-47-48, then 47-48-49, 47-48-49-50 and so on in groups consisting of 3-4 consecutive values. Since I didn’t understand the algorithm, it looks suspiciously like backtracking search for me. It can be helpful if you explain why it isn’t exponential.
На хабре интересная ветка: http://habrahabr.ru/blogs/computer_science/112161/#comment_3...
Оставить комментарий
Dimon89
Группа учёных из Владимира опубликовала открытое письмо с решением задачи 3-SAT. Более того, они построили практическую реализацию, которая, как утверждается, работает за полиномиальное время.PS О, нашёл более полную русскую версию на хабре