P-Optimal Algorithms / Local versus Global Satisfaction

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
}

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}
}

Hastad's Work

Emo Welzl's Lecture Notes on Satisfiability

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
}

Luca Trevisan's work

@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

Further Closely Related Work

@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},
} 

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}
}