Ravi Sundaram initiated and commented on this discussion and Raj Rajaraman helped me greatly in getting the facts right after 20 years in the software design field. This page assumes that readers are familiar with our 1981 JACM paper [Lieberherr/Specker 1981] on Partial Satisfaction and the Journal of Algorithms paper:
@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
}
that simplifies and generalizes the initial result.
The purpose of this page is to view Johan Hastad's seminal and influential work on optimal inapproximability results (STOC and 60 page JACM paper) in a more general context and to show that an earlier result of ours, proved using simpler techniques than PCP (probabilistically checkable proof) and Fourier analysis, is a consequence of one of Hastad's key results.
Informally, we call an algorithm P-optimal if "improving" it would imply that P=NP. There are two kinds of P-optimal algorithm theories for the generalized satisfiability problems:
TOTAL-P-optimal and OPTIMAL-P-optimal.
Fix a generalized satisfiabilty problem S with P-optimal threshold t[S].
TOTAL-P-optimal: Find an assignment that satisfies as many clauses as possible and prove that the fraction t(S)+e of the total number of clauses is always satisfied.
Example: Consider the following generalized satisfiability problem S: All clauses are an instance of the relation x+y+z=1 (exactly one of the variables is 1). Then t[S] = 4/9. Note that a random assignment will only satisfy 3/8!
OPTIMAL-P-optimal: Find an assignment that satisfies as many clauses as possible and prove that the fraction t[S]+e of the optimal number of satisfiable clauses is always satisfied.
TOTAL-P-optimal has been addressed in a general way around 1980 by Lieberherr, Specker et al. [JACM, Journal of Algorithms, Theoretical Computer Science]. Both P-optimal algorithms and their optimality proofs were developed.
The results in Johan Hastad's far-ranging and seminal 1997 STOC paper can be seen to address OPTIMAL-P-optimal for a few interesting special cases. Hastad's work shows that the algorithms are P-optimal in a second and stronger way using the thresholds that have been known before. The STOC paper was followed by a JACM paper: J. Hastad, Some optimal inapproximability results, Journal of ACM, Vol. 48, 2001, pp 798--859.
begin Example:
[Lieberherr/Specker 1981]
shows that it is NP-hard to determine in polynomial time whether
there exists an assignment that satisfies 7/8+eps of the TOTAL number of
clauses in a given 3SAT formula.
On the other hand, Hastad shows that it is NP-hard to determine in
polynomial time, an assignment that satisfies 7/8+eps of the OPTIMAL
number of satisfiable clauses in a given 3SAT formula.
For both the problems, if we replace 7/8+eps by 7/8, then it is trivial to solve them -- since for any formula, there exists an assignment that satisfies 7/8 of the clauses. (We assume that every clause has exactly 3 literals.)
The reduction in [Lieberherr/Specker 1981] takes a 3SAT formula f and pads a few copies of f with several copies of an 8-clause formula for which only 7 clauses can be satisfied. And the reduction shows that if one can determine whether 7/8+eps of the clauses in this padded formula can be satisfied, then one can determine whether f is satisfiable.
However, the reduction will not work for Hastad's problem. This is
because the optimal number of satisfiable clauses in the padded formula is
only a 7/8+delta fraction, where delta is small. Since one can find an
assignment that satisfies 7/8 fraction of all formulas, we obtain a near
1-approximation. (In fact, any assignment will give a near
1-approximation.)
end Example
Conjecture TOTAL = OPTIMAL: The TOTAL-P-optimal thresholds are the same as the OPTIMAL-P-optimal thresholds. In other words, if the TOTAL-P-optimal threshold is t[S] for generalized satisfiability problem S, then for all e it is NP-hard to find an assignment that satisfies the fraction t[S]+e of the OPTIMAL number of satisfiable clauses in a given S formula.
Johan Hastad's results confirm this conjecture for the cases he covered.
Next we show how Hastad's work implies our older results:
Johan Hastad proves using PCP techniques:
> Theorem 5.6 page 39: > > For any e>0 it is NP-hard to distinguish satisfiable E3-SAT > formulas from at most 7/8 + e satisfiable E3-SAT formulas.
We generalize this to:
Conjecture Hastad-Generalized: Fix a generalized satisfiabilty problem S with P-optimal threshold t[S]. For any e>0 it is NP-hard to distinguish satisfiable S formulas from at most t[S] + e satisfiable S formulas.
Proposition: Conjecture Hastad-Generalized => TOTAL P-optimal
Proof: Assume there is a polynomial algorithm for the decision problem in TOTAL P-optimal. Then there is a polynomial algorithm for the decision problem in Conjecture Hastad-Generalized. Given a formula s of satisfiability problem S for which we want to know whether s is satisfiable or whether it is at most t[S] + e satisfiable, we do the following: Ask TOTAL P-optimal, whether at least the fraction t[S] + e of the clauses can be satisfied. If no, we say "at most t[S] + e satisfiable". If yes, we use the reduction shown earlier to find out whether s is satisfiable.
Conclusions: We conjecture that Hastad's work can be generalized and we show how Hastad's work implies an earlier result that can be proven with much simpler techniques. Hastad's work provides a stronger kind of proof of P-optimality. Algorithm MAXMEAN presented in the Journal of Algorithms paper gives much better results than what a random assignment will satisfy. It would be interesting to know whether all those problems are not approximable beyond the maximum random assignment threshold guaranteed by algorithm MAXMEAN.
References: [Lieberherr/Specker 1981] Complexity of Partial Satisfaction JACM 1981 J. Hastad, Some optimal inapproximability results, Journal of ACM, Vol. 48, 2001, pp 798--859. Not referenced but closely related: M. Yannakakis, On the approximation of maximum satisfiability, J. Algorithms 17 (1994), 475-502. M. X. Goemans and D. P. Williamson, New 3/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math., 7 (1994), 656-666.For further references: Main P-optimal page