Width-parameterized SAT: Time-Space Tradeoffs

Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou +1

Width parameterizations of SAT, such as tree-width and path-width, enable the study of computationally more tractable and practical SAT instances. We give two simple algorithms. On…