Microsoft Research picks up a theme on which I worked in the late seventies and early eighties: Transition points for NP-complete problems: points where easy problems suddenly become hard to solve, or vice versa. (see IEEE Computer, January 1998, page 58.) There are two kinds of transition points: phase transition points, based on parameter-controlled randomly generated instances, and dichotomy transition points, based on a continuous parameter that has a transition point where the complexity switches from polynomial to NP-complete. Our work is in the space of dichotomy transition points. If you are interested in phase transition points, according to Berthe Choueiry, work on the phase transition in CSP has seen a big boom after a 1991 paper by Cheeseman, Kanefsky and Taylor.

The theory of P-optimal algorithms is about finding transition points for a large family of constraint-based decision problems (generalized satisfiability problems where any set of finite relations may be used to express the constraints and where all variables have the same domain). The transition points are of the nature: We have a set of instances I(f) for f a real number ranging between 0 and 1. Evergreen Game or Evergreen Game for Life Scientists.

Microsoft Research picks up a theme on which I worked in the late seventies and early eighties: Transition points for NP-complete problems: points where easy problems suddenly become hard to solve, or vice versa. (see IEEE Computer, January 1998, page 58.) There are two kinds of transition points: phase transition points, based on parameter-controlled randomly generated instances, and dichotomy transition points, based on a continuous parameter that has a transition point where the complexity switches from polynomial to NP-complete. Our work is in the space of dichotomy transition points. If you are interested in phase transition points, according to Berthe Choueiry, work on the phase transition in CSP has seen a big boom after a 1991 paper by Cheeseman, Kanefsky and Taylor.

The theory of P-optimal algorithms is about finding transition points for a large family of constraint-based decision problems (generalized satisfiability problems where any set of finite relations may be used to express the constraints and where all variables have the same domain). The transition points are of the nature: We have a set of instances I(f) for f a real number ranging between 0 and 1. For instances I(f) the problem is easy if f < T (T a transition point) and for instances I(f) the problem is NP-complete if f >= T+e for e arbitrarily small.

Ernst Specker and I developed this theory in the late 1970's and early 1980's at ETH Zurich and it was completed at Princeton University. Our initial paper was the Golden Ratio result for the Satisfiability Problem which was published at FOCS and in the Journal of the ACM. Lieberherr/Specker JACM 1981

@ARTICLE{lieber-specker:partial-1, TITLE = "Complexity of Partial Satisfaction", AUTHOR = "Karl J. Lieberherr and Ernst Specker", JOURNAL = "Journal of the Association for Computing Machinery", YEAR = 1981, PAGES = "411-421", VOLUME = 28, NUMBER = 2 }This paper used basic number theory (Bertrand's theorem) and the theory of multiply transitive permutation groups to solve the problem. A later paper in the Journal of Algorithms simplified the proof and generalized the approach to the generalized satisfiability problem proposing an algorithm called MAXMEAN. See reference lieber:algorithms. MAXMEAN is summarized in: http://www.ccs.neu.edu/home/lieber/p-optimal/partial-sat-II/ and an elegant introduction based on a lecture by David Williamson is provided for easier access to the key ideas.

MAXMEAN uses the Method of Conditional Expectations by Erdoes and Selfridge to make a probabilistic algorithm deterministic. MAXMEAN is actually a family of algorithms, one algorithm for each fixed family of relations. MAXMEAN has the desirable property that it is uniform and does not require specialized techniques for different sets of relations. An empirical comparison of MAXMEAN with other MAXSAT algorithms is in preparation.

Follow-on papers were with Steve Vavasis and Ming-Deh Huang. The paper with Ming-Deh Huang (Theoretical Computer Science) considered generalized satisfiability problems with forbidden substructures and how the forbidden substructures influence the transition point.

It is interesting that Microsoft Research does more work in this area. They have a Fields Medal winner (the highest prize in mathematics) working on transition points for NP-complete problems.

Viewgraphs on P-optimal algorithms are available: PowerPoint version, PostScript version. Note that a random assignment will only satisfy 3/8 of the conditions. Therefore, the P-optimal threshold must be equal or greater than 3/8. The viewgraphs show that it is 4/9 for the "One-in-three satisfiability" problem. Poster explaining P-optimality with biased coins.

Latest unpublished paper by Ernst Specker and Karl Lieberherr on Complexity of Partial Satisfaction II. Work done at Princeton University, GTE Laboratories and ETH Zurich. Completed in 1985. See also Reviews etc. for latest unpublished paper by Ernst Specker and Karl Lieberherr Norbert Hungerbuehler from ETH rediscovered the paper and it is now published in the "Elemente der Mathematik" in a special issue on "Remembering Ernst Specker" (Erwin Engeler, Norbert Hungerbuehler and Johann Makowsky, Coordinating Editors).

@ARTICLE{lieber-specker:partial-2, TITLE = "{Complexity of Partial Satisfaction II}", AUTHOR = "Karl J. Lieberherr and Ernst Specker", JOURNAL = "Elemente der Mathematik", YEAR = 2012, PAGES = "134-150", VOLUME = 67, NUMBER = 3, doi = {10.4171/EM/202} }

See also his Satisfiability Updates for the latest developments.

References.

Some key papers are online for personal use.

@ARTICLE{lieber:algorithms, AUTHOR = "Karl J. Lieberherr", TITLE = "Algorithmic extremal problems in combinatorial optimization", JOURNAL = "Journal of Algorithms", YEAR = 1982, PAGES = "225-244", VOLUME = 3 } http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-4D7JMY4-2X&_coverDate=09%2F30%2F1982&_alid=439770433&_rdoc=1&_fmt=&_orig=search&_qd=1&_cdi=6839&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=35ebd083ebc05f16cc549738dbdd4987 An alternate title for the above paper would be: On the approximation of generalized maximum satisfiability Later work on this topic: M. Yannakakis, On the approximation of maximum satisfiability, J. Algorithms 17 (1994), 475-502. @ARTICLE{lieber-huang:tcs-85, AUTHOR = "M.A. Huang and Karl J. Lieberherr ", TITLE = "Implications of forbidden structures for extremal algorithmic problems", JOURNAL = tcs, VOLUME = 40, YEAR = 1985, PAGES = "195-210" } @ARTICLE{lieber-vavasis:dortmund, AUTHOR = "Karl J. Lieberherr and S. Vavasis", TITLE = "Analysis of polynomial approximation algorithms for constraint expressions", JOURNAL = lncs, YEAR = 1983, PAGES = "187-197", VOLUME = 145 }

@article{984912, author = {Luca Trevisan}, title = {On Local Versus Global Satisfiability}, journal = {SIAM J. Discret. Math.}, volume = {17}, number = {4}, year = {2004}, issn = {0895-4801}, pages = {541--547}, doi = {http://dx.doi.org/10.1137/S0895480197326528}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, } See also the earlier versions: http://academic.research.microsoft.com/Paper/155910.aspx http://citeseer.ist.psu.edu/cache/papers/cs/1219/http:zSzzSzwww.cs.columbia.eduzSz~lucazSzpubszSzlocal.pdf/trevisan97local.pdf

@article{Dvorak:2005:LCC:1132633.1132637, author = {Dvo\v{r}\'{a}k, Zden\v{e}k and Kr\'{a}l, Daniel and Pangr\'{a}c, Ond\v{r}ej}, title = {Locally consistent constraint satisfaction problems}, journal = {Theor. Comput. Sci.}, issue_date = {8 December 2005}, volume = {348}, number = {2}, month = dec, year = {2005}, issn = {0304-3975}, pages = {187--206}, numpages = {20}, url = {http://dx.doi.org/10.1016/j.tcs.2005.09.012}, doi = {10.1016/j.tcs.2005.09.012}, acmid = {1132637}, publisher = {Elsevier Science Publishers Ltd.}, address = {Essex, UK}, keywords = {2-SAT, CNF formulas, boolean predicates, constraint satisfaction problems}, }2012 improvement of the Lieberherr-Specker bound (in Algorithmica) with applications to fixed-parameter-tractable (FPT) algorithms.

See: http://rd.springer.com/article/10.1007/s00453-011-9550-1

@article{, year={2012}, issn={0178-4617}, journal={Algorithmica}, volume={64}, issue={1}, doi={10.1007/s00453-011-9550-1}, title={A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Applications}, url={http://dx.doi.org/10.1007/s00453-011-9550-1}, publisher={Springer-Verlag}, keywords={MaxSat; Lower bound; 2-Satisfiable; Fixed parameter tractable; Kernel}, author={Crowston, Robert and Gutin, Gregory and Jones, Mark and Yeo, Anders}, pages={56-68}, language={English} }

Added 2012

The topic of local versus global satisfaction continues to generate interesting papers. The most surprising result was the paper by Luca Trevisan \cite{984912} (see below) which showed that the global satisfaction ratio only approaches 3/4. Links to several other related papers are on the page \cite{LieberherrSpecker:1985-2012:PartialSatisfaction} (see below).

@article{984912, author = {Luca Trevisan}, title = {On Local Versus Global Satisfiability}, journal = {SIAM J. Discret. Math.}, volume = {17}, number = {4}, year = {2004}, issn = {0895-4801}, pages = {541--547}, doi = {http://dx.doi.org/10.1137/S0895480197326528}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, } @MISC{LieberherrSpecker:1985-2012:PartialSatisfaction, author = {Lieberherr, Karl}, title = {Work by Karl Lieberherr and Ernst Specker on Partial Satisfaction}, month = jun, year = {2012}, howpublished={\url{http://www.ccs.neu.edu/home/lieber/p-optimal/README.html}} } @ARTICLE{lieber-specker:partial-2, TITLE = "{Complexity of Partial Satisfaction II}", AUTHOR = "Karl J. Lieberherr and Ernst Specker", JOURNAL = "Elemente der Mathematik", YEAR = 2012, PAGES = "134-150", VOLUME = 67, NUMBER = 3, doi = {10.4171/EM/202} }

Professor Karl J. Lieberherr College of Computer and Information Science, Northeastern University Internet: lieberherr AT ccs DOT neu DOT edu