What makes normalized weighted satisfiability tractable

Iyad Kanj, Ge Xia

We consider the weighted antimonotone and the weighted monotone satisfiability problems on normalized circuits of depth at most $t\ge 2$, abbreviated {\sc wsat${}^{-}[t]$} and {\sc w…