Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MAXSAT:
Reports tagged with MaxSAT:
TR20-082 | 23rd May 2020
Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals

MaxSAT Resolution and Subcube Sums

Revisions: 2

We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weakening (the system MaxResW), p-simulates tree-like resolution. In devising a lower bound technique specific to MaxRes (and not merely inheriting lower bounds from ... more >>>




ISSN 1433-8092 | Imprint