Что такое SAT и для чего он хорош?
Недавно я увидел на Reddit статью об использовании SAT для решения головоломки [1]. Это заставило меня очень заинтересоваться этой штукой "SAT". Я прочитал статью в Википедии, но хотел бы попросить кого-нибудь из вас объяснить мне это более простым языком.
Что такое SAT и для чего он нужен? Можно ли его использовать для обхода древовидной структуры? Для синтаксического анализа текстов? Для переноса строк [2]? Для упаковки корзин [3]? Является ли это разновидностью техники оптимизации?
В связи с этим я читал, что NP vs P - это выбор чисел из множества, которые в сумме равны нулю, и проверка того, равны ли некоторые числа нулю - имеет ли SAT какое-то отношение к этому?
[1] http://www.reddit.com/r/programming/comments/pxpzd/solving_hexiom_really_fast_with_a_sat_solver/