@TECHREPORT{CPS-II-rep, AUTHOR = "Karl Lieberherr and Ernst Specker", TITLE = "Complexity of Partial Satisfaction II", INSTITUTION = "Princeton University, Dept. of EECS", YEAR = 1982, NUMBER = "293", Note = "http://www.ccs.neu.edu/research/demeter/biblio/partial-sat-II.html" } @UNPUBLISHED{lieber-specker:partial-2, TITLE = "Complexity of Partial Satisfaction II", AUTHOR = "Karl J. Lieberherr and Ernst Specker", YEAR = 1985 }

Notes by Karl:

A follow-on paper to the Journal of the ACM paper. Indicates that determining the P-optimal thresholds requires ingenuity. Presents the results of the JACM paper in a general context. The paper exists in two incarnations, one from January 1982 and one from 1985. Partial-SAT2.pdf is the newer version from 1985 and complexity.pdf is the older version from 1982 (Princeton Unversity Technical Report). Both versions contain valuable information. For example, the older version contains a section 6 about solving minmax problems which is omitted from the later version.

The paper was submitted to the SIAM Journal on Computing and we got back the following wonderful review:

This seems to be the ultimate result along the cores of research of Lieberherr/Specker. It gives a closed form to a natural problem which is stated in a way which makes its significance to complexity theory clear. The theorme's proof is a beautiful and tricky kind of good mathematics and a brilliant example of good math, rightly applied in computer science. Also very well written.The paper was not accepted by the journal because a second reviewer wrote:

The paper is not well written. I had tremendous difficulty trying to understand certain points.I then went into the exciting world of hardware description languages and structure-shy programming and lost interest in publishing the paper.