@importpdf: images/SAT

I briefly comment on some intuition for recognizing special cases of SAT which are solvable in polynomial time

• 2SAT / Horn SAT : implication following
• clauses can be phrased as linear equations mod 2 can be solved by gaussian elimination
• DP can solve some nested things
• euler tour can solve some weird cases