Integrating Superresolution and P-Optimality in Boolean MAX-CSP

After a long absence from Satisfiability research, we re-enter the field from the point of view of empirical algorithmics (see e.g. http://www.cs.ubc.ca/~hutter/EARG.shtml).

This paper explains Superresolution in the form of a transition system. The presentation is different, but the concept is still the same as in 1977.

@TECHREPORT{SuperP-optimal:Jan-07,
AUTHOR = "Ahmed Abdelmeged and Christine D. Hang and Daniel Rinehart and Karl J. Lieberherr",
TITLE = "{Superresolution and P-Optimality in Boolean MAX-CSP Solvers}",
INSTITUTION = "Northeastern University",
YEAR = 2007,
MONTH = "January",
NUMBER = "NU-CCIS-07-01"
}

Paper.

RelationTable gives details of how the compact representation works for rank 3. Table produced by Ahmed Abdelmeged.

256 Look-Ahead Polynomials for rank 3. The assignment N is all false. Equivalent to the 256 appmean polynomials for rank 3. On the horizontal axis 0.5 corresponds to 0 and 10.5 corresponds to 1. Produced by Ahmed Abdelmeged.