Accumulating Pruning Constraints: New Exact Polynomial-Space Algorithms for Max 2-SAT.

arXiv:2610.39992v1 Announce Type: cross Abstract: We present deterministic polynomial-space algorithms that solve Max 2-SAT on $n$ variables exactly in time $\Ostar(2^{(1-\gamma)n})$, for a fixed $\gamma>0$, on several classes of instances whose clause density