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 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 from Berkeley solved the k-satisfiability problem
for CNF formulas. The answer is 3/4.
@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},
}
Professor Karl J. Lieberherr College of Computer and Information Science, Northeastern University Internet: lieberherr AT ccs DOT neu DOT edu