\documentclass{article} \parindent=0mm \parskip=2mm \usepackage{amsmath} \setlength{\topmargin}{-1cm} \setlength{\headheight}{1.5cm} \setlength{\headsep}{0.3cm} \setlength{\textheight}{23.5cm} \setlength{\oddsidemargin}{0.5cm} \setlength{\textwidth}{15cm} \begin{document} {\bf\LARGE Complexity of Partial Satisfaction II} Karl Lieberherr\footnote{Supported by National Science Foundation grant MCS80-04490 and Forschungsinstitut f\"ur Mathematik, ETH Zurich. Most of this research was done while the first author was at Princeton University.} and Ernst Specker \section*{Abstract} What is easy and when does it become hard to find a solution of a problem? We give a sharp answer to this question for various generalizations of the well-known maximum satisfiability problem. For several maximum $\psi$-satisfiability problems we explicitly determine algebraic numbers $\tau_\psi$ ($0 < \tau_\psi < 1$), which separate NP-complete from polynomial problems. The fraction $\tau_\psi$ of the clauses of a $\psi$-formula can be satisfied in polynomial time, while the set of $\psi$-formulas which have an assignment satisfying the fraction $\tau'$ ($\tau' > \tau_\psi$, $\tau'$ rational) of the clauses is NP-complete. \section{Introduction} We continue our study of the (generalized) satisfiability problem [Lieberherr/Specker (1981), Lieberherr (1982)]. One often recurring theme in computer science is the following: Given an algorithmic problem, find an algorithm which is optimal with respect to a certain measure. The motivation for looking for such algorithms is that the algorithm designer has a guarantee that his algorithm is best-possible in a certain precise sense. Some typical measures are time, space, comparisons, $A\cdot T^2$ etc. For many measures it is hard to prove that a given algorithm is optimal. We have analyzed the algorithmic problem of finding good approximate solutions for generalized satisfiability problems. The measure we used to compare algorithms is the quality of the approximations which they find. In [Lieberherr (1982)] we describe an efficient algorithm MAXMEAN* which is best possible with respect to our measure for a large class of problems. In this paper we provide a framework for the analysis of MAXMEAN* and we apply our method to several special cases. We investigate combinatorial optimization problems of the following form: Given a sequence of constraints, find an assignment which satisfies as many as possible. This constraint satisfaction problem appears in many applications like time table scheduling, laying out graphs in a grid, decoding of linear codes, minimizing PLA's etc. Maximization problems of this type are naturally formulated as maximum $\psi$-satisfiability problems [Schaefer (1978)]. $\psi$ is a finite set of logical relations $R_1,\ldots,R_m$ which are used to express the constraints. A $\psi$-formula $S$ with $n$ variables is a finite sequence of clauses each of the form $R_i(x_1,\ldots,x_{r_i})$. $r_i$ is the rank of $R_i$ and $x_1,\ldots,x_{r_i}$ are a subset of the variables of $S$. The maximum $\psi$-satisfiability problem consists of finding, for any $\psi$-formula $S$, an assignment to the $n$ variables satisfying the maximum number of the clauses. Let $\tau_\psi$ be the fraction of the clauses which can be satisfied efficiently in any $\psi$-formula $S$. It is shown in [Lieberherr (1982)] that the following algorithm MAXMEAN* guarantees to satisfy the fraction $\tau_\psi$ in time $O ( | S | | \operatorname{clauses}(S) | )$, where $| \operatorname{clauses}(S) |$ is the number of clauses in $S$. \subsection*{Algorithm MAXMEAN*} \begin{tabbing} Output: \= An assignment satisfying at least the fraction 7", of the clauses.\kill Input: \> A $\psi$-formula $S$ with $n$ variables.\\ Output: \> An assignment satisfying at least the fraction $\tau_\psi$ of the clauses. \end{tabbing} \begin{tabular}{p{.05\linewidth}p{.05\linewidth}p{.9\linewidth}} \multicolumn{3}{l}{{\em max\_assignment} $:=0$ ;} \\ \multicolumn{3}{l}{{\bf loop}} \\ & \multicolumn{2}{l}{compute $k$ such that}\\ & & $\max\limits_{0\le k'\le n}$ {\em mean}$_{k'}(S ) = $ {\em mean}$_k(S)$ \\ & \multicolumn{2}{p{.9\linewidth}}{$\{$ {\em mean}$_k (S)$ is the average fraction of satisfied clauses in $S$ among all assignments having exactly $k$ ones. {\em mean}$_k (S)$ is a polynomial in $k$ which can be efficiently computed $\}$}\\ & \multicolumn{2}{l}{{\bf for} all variables $x \in S$ {\bf do}}\\ & & {\bf if} {\em mean}$_{k-1}(S_{x=1}) > $ {\em mean}$_{k}(S_{x=0})$\\ & & {\bf then} $J [x ] := 1; k :=k -1; S :=S_{x=1}$\\ & & {\bf else} $J [x ] := 0; S :=S_{x=0}$ \\ & & $\{$ {\em mean}$_{-1}(S )=$ {\em mean}$_{0}(S )$, {\em mean}$_{n+1}(S )=$ {\em mean}$_n (S) \}$\\ & \multicolumn{2}{p{.9\linewidth}}{$h :=$ {\em SATISFIED}$(S ,J); \{$ {\em SATISFIED}$(S,J)$ is the number of satisfied clauses in $S$ under assignment $J$ $\}$}\\ & \multicolumn{2}{p{.9\linewidth}}{{\bf if} $h >$ {\em max\_assignment} {\bf then} {\em max\_assignment} $:=h$ {\bf else exit} ;}\\ & \multicolumn{2}{p{.9\linewidth}}{rename all variables in $S$ which are assigned 1 by $J$ ;}\\ \multicolumn{3}{l}{{\bf end ;}} \end{tabular} Already after one iteration of the outermost loop of MAXMEAN* the fraction $\tau_\psi$ of the clauses is satisfied by assignment $J$ [Lieberherr (1982)]. From the definition of $\tau_\psi$ it follows that MAXMEAN* is a polynomial $(1-\tau_\psi)$-approximate algorithm for the maximum $\psi$-satisfiability problem, i.e. MAXMEAN* comes within $1-\tau_\psi$ of the optimal assignment. It is an open problem whether there are polynomial $\epsilon'$-approximate algorithms for $\epsilon' <1-\tau_\psi$. However it is shown in [Lieberherr (1982)] that it is NP-complete to decide whether more than the fraction $\tau_\psi$ of the clauses can be satisfied in a given $\psi$-formula. In the following we outline the contents of this paper. In [Lieberherr (1982)] we reduce the determination of $\tau_\psi$ for a given $\psi$ to a discrete minimax problem. We show, that the discrete minimax problem can be reduced to a continuous minimax problem which is considerably easier to solve (Theorem 2.1). We determine $\tau_\psi$ for several maximum $\psi$-satisfiability problems, each requiring a different proof technique. In Theorem 3.1 we analyze special systems of linear inequalities, i.e.~a special case of the $(0,1)$-integer programming problem. {\bf Theorem 3.1}\quad Let $R_j$ be the relation of rank $r$ which holds, if exactly $j$ of the $r$ variables are assigned one. Let $\psi=\{R_0, \ldots ,R_r \}$. Then algorithm MAXMEAN* satisfies the fraction $\frac1{r+1}$ of the clauses in a $\psi$-formula $S$ in time $O ( | S | | \operatorname{clauses}(S) | )$. The set of $\psi$-formulas having an assignment satisfying the fraction $\tau' > \frac1{r+1}$ of the clauses is NP-complete ($\tau'$ rational). \bigskip The proof first uses the above reduction (Theorem 2.1) and continues with an averaging trick which simplifies a part of the problem to the computation of an integral. The integral is solved by partial integration. The mean value theorem from calculus and some further minimax manipulations complete the proof. The following theorem analyzes subclasses of the regular satisfiability problem. {\bf Theorem 4.1}\quad Let $F (p ,q )$ be the class of propositional formulas in conjunctive normal form which contain in each clause at least $p$ positive or at least $q$ negative literals ($p ,q > 1$). Let $\alpha$ be the solution of $(1-x)^p =x^q$ in $(0,1)$ and let $\tau_{p,q}=1-\alpha^q$. Then algorithm MAXMEAN* satisfies the fraction $\tau_{p ,q}$ of the clauses in any formula $\in F (p ,q)$ in time $O ( | S | | \operatorname{clauses}(S) | )$. The set of formulas $\in F (p ,q)$ which have an assignment satisfying the fraction $\tau' > \tau_{p ,q}$ of the clauses is NP-complete ($\tau'$ rational). \bigskip The proof is involved and is decomposed into 3 simplifying reductions. In the last part of the paper we partially solve a problem which was left open in [Lieberherr/Specker (1981)]. We give an efficient algorithm which guarantees to satisfy 2/3 of the clauses in a 3-satisfiable conjunctive normal form. \section{Reduction to a continuous min-max-problem} In the following we sketch how the computation of $\tau_\psi$ can be simplified to a discrete minimax problem involving polynomials (a more detailed explanation is in [Lieberherr (1982)]). $\tau_\psi$ is by definition the fraction of the clauses which can be satisfied in all $\psi$-formulas. First we consider $\psi$-formulas with at most $n$ variables and let $\tau_{n,\psi}$ be the fraction of clauses which can be satisfied in all such formulas. For computing $\tau_{n,\psi}$ we determine the worst-case formulas, i.e.~the formulas where the smallest fraction of the clauses can be satisfied (by the optimal assignment) among all $\psi$-formulas with $n$ variables. It is easy to prove that these formulas are symmetric, i.e.~they are invariant under permutations of the variables, up to a permutation of the clauses. Fortunately the worst-case formulas have a nice structure and therefore it is easy to compute an optimal assignment for them. For computing an optimal assignment for a symmetric formula we only have to compute the maximum of a polynomial. This polynomial can be derived by elementary combinatorial analysis. In this section we prove a theorem which simplifies the computation of $\tau_\psi$ to the solution of a continuous minimax problem which does not involve a limit operation. Let $\psi= \{R_1 ,R_2, \ldots , R_m\}$ be a finite set of relations and let $S$ be a symmetric $\psi$-formula in which the fraction $t_{R_i}$ of the clauses contains clauses involving relation $R_i$. In order to compute $\tau_{n,\psi}$ we have to find the worst assignment to the parameters $t_{R_1} \ldots t_{R_m}$ which makes the optimal fraction of satisfiable clauses as small as possible. It follows from the above discussion that (assuming that $\sum\limits_{i=1}^m t_{R_i} = 1$, $t_{R_i} \ge 0$ $(1\le i\le m)$) \begin{eqnarray*} \tau_\psi &=& \lim_{n\to \infty} \tau_{n,\psi}\\ \tau_{n,\psi} &=& \min_{{t_{R_i} \text{ rational}}\atop{1\le i\le m}}\ \max_{{0\le k\le n}\atop{\text{integer}}}\ \sum_{i=1}^m t_{R_i}\cdot SAT_k^n(R_i)\\ SAT_k^n(R) &=& \sum_{s=0}^{r(R)} \frac{q_s(R)}{r(R)_s} \frac{(k)_s (n-k)_{r(R)-s}}{(n)_{r(R)}} \end{eqnarray*} where \begin{tabular}{p{.05\textwidth}p{.95\textwidth}} $t_R$ & is the fraction of clauses containing relation $R$\\ $r(R)$ & is the rank of $R$\\ $q_s (R )$ & is the number of satisfying rows in the truth table of $R$ which contains $s$ ones\\ $(\alpha)_\beta$ & $\frac{\alpha !}{\beta!(\alpha-\beta)!}$, where $\alpha,\beta$ are positive integers, $\alpha\ge \beta$. \end{tabular} Let \begin{eqnarray*} \tau'_\psi &=& \min_{{t_{R_i} \text{ real}}\atop{1\le i\le m}}\ \max_{{0\le x\le 1}\atop{\text{real}}}\ \sum_{i=1}^m t_{R_i}\cdot SAT_x(R_i),\qquad \sum_{i=1}^m t_{R_i} =1, t_{R_i} \ge 0\\ appSAT_x(R) &=& \sum_{s=0}^{r(R)} q_s(R) x^s (1-x)^{r(R)-s}. \end{eqnarray*} {\bf Theorem 2.1}\quad $ \tau_\psi = \tau'_{\psi}\,. $\bigskip $\tau_\psi$ is defined as the solution of a discrete minimax problem since the maximization is over integers. However $\tau'_\psi$ is expressed as the solution of a continuous minimax problem since both the minimization and maximization are over reals. Furthermore the formula for $\tau'_\psi$ does not involve a limit operation. Therefore the definition of $\tau'_\psi$ is easier to evaluate. We need the following definitions for the proof of Theorem 2.1. Let $S$ be a $\psi$-formula containing relation $R_i$ ($1 \le i \le m$) for the fraction $t_{R_i}$ of the clauses. Let $\vec t = (t_{R_1}, \ldots , t_{R_m})$. $$ {\text{\em mean}}_k^n(\vec t) = \sum_{i=1}^m t_{R_i} SAT_k^n(R_i). $$ Let $$ {\text{\em appmean}}_x(\vec t) = \sum_{i=1}^m t_{R_i} appSAT_x(R_i). $$ {\bf Lemma 2.2}\quad Let $\psi$ be a finite set of $m$ relations and let $\vec t = (t_{R_1}, \ldots, t_{R_m} )$ be a vector whose components add up to 1. \begin{enumerate} \item[(1)] $\lim\limits_{j\to\infty}${\em mean}$_{j\cdot k}^{j\cdot n} (\vec t) =$ {\em appmean}$_{k/n}(\vec t)$ \item[(2)] For all real $x$ ($0\le x \le 1$): $$ \lim_{n\to\infty}{\text{\em mean}}^n_{\lceil nx\rceil}(\vec t) = {\text{\em appmean}}_x (\vec t) $$ \end{enumerate} {\bf Proof}\quad (1) We have to show that $$ \lim_{j\to\infty} \frac{(jk)_s (j(n-k)_{r-s}}{(jn)_r}= \left(\frac kn\right)^s \left( 1-\frac kn\right)^{r-s}. $$ This follows from $$ \lim_{j\to\infty} \frac{(jk)(jk-1)\dots(jk-s+1)}{(jn)(jn-1)\dots(jn-s+1)}=\left(\frac kn\right)^s $$ and $$ \lim_{j\to\infty} \frac{(j(n-k))(j(n-k)-1)\dots(j(n-k)-r+s-1)}{ (jn-s)(jn-s-1)\dots(jn-r+1) }=\left(1-\frac kn\right)^{r-s} $$ (2) Follows from $$ \lim_{n\to\infty}\frac{\lceil nx\rceil}n = x $$ and (1). {\bf Proof of Theorem 2.1}\quad We have to show that for any $\vec t$ \begin{eqnarray*} A &=& \lim_{n\to\infty} \max_{{0\le k\le n}\atop{\text{integer}}} {\text{\em mean}}_k^n(\vec t) =\\ B &=& \max_{{0\le x\le 1}\atop{\text{real}}} {\text{\em appmean}}_x(\vec t). \end{eqnarray*} Let $x_{\max}$ be the maximal $x$ in the definition of $B$. For each $n$, define $k (n )= \lceil x_{\max} \rceil$. Then by Lemma 2.2(2) $$ A\ge \lim_{n\to \infty} {\text{\em mean}}_{k(n)}^n (\vec t) = {\text{\em appmean}}_{x_{\max}}(\vec t) = B. $$ Hence $A \ge B$. To show that $A \le B$, define the sequence $k (n )$, $n =1,2,\ldots$, such that {\em mean}$_{k(n)}^n(\vec t)=\max\limits_{0\le k\le n}${\em mean}$_k^n(\vec t)$. Let $k'(n')$, $n'$ ranging over an increasing subsequence of the natural numbers, be an infinite subsequence of $k (n)$ such that $$ \lim_{n'\to\infty}\frac{k'(n')}{n'} = x $$ for some real $x$. Then by Lemma 2.2(2) $$A = \lim_{n'\to\infty} {\text{\em mean}}_{k'(n')}^{n'} (\vec t) = \lim_{n\to\infty} {\text{\em mean}}^n_{\lceil xn\rceil} (\vec t)= {\text{\em appmean}}_x (\vec t) \le B. $$ \section{Special $(0,1)$-Integer Programming} In this section we analyze special systems of linear equalities. The computation of the constant $\tau_\psi$ for this case requires new methods. One reason is that here we are dealing with sets of relations which contain $r$ relations ($r$ a variable) and not just two relations. Let $R_j$ be the relation of rank $r$ which holds if exactly $j$ of the $r$ variables are true. {\bf Theorem 3.1}\quad Let $\psi = \{R_0,R_1, \ldots, R_r \}$. Then \begin{enumerate} \item[(i)] In any $\psi$-formula the fraction $\frac1{r+1}$ of the clauses can be satisfied. \item[(ii)] There is a polynomial algorithm MAXMEAN* which finds an assignment satisfying at least the fraction $\frac1{r+1}$ of the clauses in a $\psi$-formula. \item[(iii)] For any rational $\tau'>\frac1{r+1}$ the set of $\psi$-formulas having an assignment satisfying at least the fraction $\tau'$ of the clauses is NP-complete. \end{enumerate} {\bf Proof of 3.1(i)}\quad Since $q_s(R_j) = 0$ if $s\neq j$ and $q_j(R_j) = \binom rj$ we have $$ {\text{\em appmean}}_x(S) = \sum_{j=0}^r t_j \binom rj x^j(1-x)^{r-j}. $$ By Theorem 1 it is sufficient to show that \begin{eqnarray*} \frac1{r+1} &=& \min_{t_j \text{ real}\atop{0\le j\le r}} \max_{{0\le x\le 1}\atop{\text{real}}} {\text{\em appmean}}_x(\vec t),\qquad \sum_{j=0}^r t_j =1 \end{eqnarray*} $\psi$ has the property that it is not necessary to choose the maximal $x$ in the above formula in order to compute $\tau_\psi = \frac1{r+1}$. Therefore we perform an averaging process in the following lemma. {\bf Lemma 3.2} $$ \int_0^1 x^j(1-x)^{r-j} dx = \frac1{\binom rj(r+1)} $$ {\bf Proof}\quad Let $$ f_{j,r}=\int_0^1 x^j(1-x)^{r-j}dx $$ We show the lemma by induction. $$ f_{0,r} = \int_0^1 (1-x)^r dx = -\frac1{r+1}(1-x)^{r+1}\Big|_0^1 = \frac1{r+1} $$ For the induction step we use partial integration \begin{eqnarray*} u &=& \frac1{j+1}x^{j+1}\\ u' &=& x^j\\ v &=& (1-x)^{r-j}\\ v' &=& -(r-j)(1-x)^{r-j-1}\\ f_{j,r} &=& \int_0^1 u'v dx = uv \Big|_0^1 -\int_0^1 uv'dx= \frac{r-j}{j+1}f_{j+1,r} \end{eqnarray*} Hence, $$ f_{j+1,r} = \frac{j+1}{r-j} f_{j,r}\qquad (0\le j \tau_{p , q}$ the set of formulas in $F (p ,q)$ having an assignment satisfying at least the fraction $\tau'$ of the clauses is NP-complete. \end{enumerate} This theorem and its proof extend the results and methods given in [Lieberherr/Specker (1981)]. The proof of Theorem 4.1(i) is given by a sequence of simplifying reductions. Each reduction is presented as a Proposition $j$. The corresponding Lemma $j$ claims that Proposition $j$ implies the previous proposition (in the first step: Theorem 4.1(i)). Theorem 4.1(ii) is a special case of a general result proven in [Lieberherr (1981)]. The proof of Theorem 4.1(iii) is based on a result by [Schaefer (1978)] and the technique given in [Lieberherr/Specker (1981)]. \subsection*{Simplifying Reductions} {\bf Proposition 4.2}\quad For all integers $n > \min(p ,q)$ and for all positive integers $t_1,t_2$ there is an integer $k$ ($0\le k \le n$) such that $g_{{\text{\em EXACT}}}(n,k,t_1,t_22)=$ $$ \frac{\frac{t_1}{(n)_p}(n-k)_p + \frac{t_2}{(n)_q}(k)_q}{t_1+t_2}\le 1-\tau_{p.q} $$ {\bf Lemma 4.2}\quad Proposition 4.2 $\implies$ Theorem 4.1(i). {\bf Proof}\quad Using the techniques given in [Lieberherr/Specker (1981)] it is easy to show that the class $F (p ,q )$ can be reduced to $F '(p ,q ) = \{$formulas having only clauses containing either exactly $p$ positive literals or exactly $q$ negative literals$\}$. Furthermore, it is sufficient to consider only symmetric formulas in $F'(p ,q )$. Let $S$ be a symmetric formula in $F'(p ,q)$ which contains $t_1$ clauses of the form $A_1 \vee A_2 \vee \ldots \vee A_p$ and $t_2$ clauses of the form $\neg A_1 \vee \neg A_2 \vee \ldots \vee \neg A_q$. Then the fraction of unsatisfied clauses if $k$ variables are set to 1 is, by elementary counting methods, given by $g_{{\text{\em EXACT}}} (n ,k ,t_1 ,t_2)$ยท Note that $g_{{\text{\em EXACT}}} (n ,k ,t_1,t_2)$ is the expected fraction of unsatisfied clauses among all assignments which set $k$ variables to 1. It is denoted by {\em mean}$'_k (S)$ for a given formula $S$. First we give an outline of the proof for Proposition 4.2. {\bf Outline:}\quad Let $x =\frac kn$ and substitute $r^s$ for any expression of the form $(r)_s$ in $g_{{\text{\em EXACT}}} (n ,k ,t_1,t_2)$. The resulting expression for the fraction of {\em unsatisfied\/} clauses is $$ g_{{\text{\em APPROX}}}(x,t_1 ,t_2) =\frac{t_1(1-x)^p+t_2 x^q}{t_1+t_2}. $$ Since for all positive integers $r ,k ,n$ ($k \le n$) $$ \frac{(k)_r}{(n)_r}\le \left(\frac kn\right)^r, $$ the inequality $$ g_{{\text{\em EXACT}}}(n,k,t_1,t_2)\le g_{{\text{\em APPROX}}}(\frac kn,t_1,t_2) $$ holds. Therefore it is sufficient to show that for all $n$ and all positive integers $t_1, t_2$ there is an integer $k$ such that $$ g_{{\text{\em APPROX}}}(\frac kn,t_1,t_2)\le 1-\tau_{p,q}. $$ W.l.o.g.~we set $t_2 = 1$, since $g_{{\text{\em APPROX}}}$ is homogeneous in $t_1,t_2$. Take the derivative of $g_{{\text{\em APPROX}}}$ with respect to $x$, set it to zero and solve for $t_1$: $$ t_1 =\frac qp\frac{x^{q-1}}{(1-x)^{p-1}} $$ Substitute for $t_1$ in $g_{{\text{\em APPROX}}}$: $$ g_{APP} (x ) = \frac{q\cdot x^{q-1} (1-x)^p + p\cdot x^q(1-x)^{p-1}}{q\cdot x^{q-1}+p(1-x)^{p-1}} $$ $g_{APP}$ has the following intuitive meaning. Consider a formula $S$ in $F' (p ,q)$ with $n$ variables and define $k_{\min}$ by $$ \min_{0\le k\le n} {\text{\em mean}}'_k(S)={\text{\em mean}}'_{k_{\min}}(S). $$ In any such a formula $S$ at most the fraction $g_{APP} (\frac{k_{\min}}{n} )$ of the clauses can be unsatisfied. This holds since the second derivative of $g_{{\text{\em APPROX}}}$ with respect to $x$ is positive if $p\ge 1$ or $q\ge 1$ and $t_1\neq 0$ and $t_2\neq 0$. Therefore it is sufficient to show that for all positive integers and all real $x$ ($0 \le x \le 1$) $$ g_{APP} (x) \le 1 - \tau_{p ,q} . $$ Compute the extremal points of $g_{APP}$ with respect to $x$ in $(0,1)$. There is only one which is given by the solution of $(1-x)^p = x^q$. Substituting $x^q$ for $(1-x)^p$ in $g_{{\text{\em EXACT}}}$ yields $$g_{{\text{\em EXACT}}} =1- x^q.$$ Therefore the fraction $\tau_{p ,q} = 1 - \alpha^q$ can be satisfied in any formula in $F' (p,q)$. The following simple heuristic method, which was also observed by John Scranton, gives the correct result. Choose $x$ such that the fraction of satisfied clauses is independent of $t_1, t_2$. The resulting condition for $x$ is $$(1-x)^p =x^q.$$ For such an $x$, the fraction of satisfied clauses is independent (in the limit) of the formula we consider and it is $\tau_{p ,q}$. Now we continue with the proof of Proposition 4.2. {\bf Proposition 4.3}\quad For all integers $n >\min(p ,q)$ and all positive integers $t_1,t_2$ there is an integer $k$ ($0\le k \le n$) such that $$ g_{{\text{\em APPROX}}} (x,t_1,t_2 ) = \frac{t_1 (1-x)^p + t_2 x^q}{t_1+t_2}\le 1-\tau_{p,q} $$ {\bf Lemma 4.3}\quad Proposition 4.3 $\implies$ Proposition 4.2. {\bf Proof}\quad Note that for all positive integers $r ,k ,n$ ($k \le n$) since \begin{eqnarray*} \frac{(k)_r}{(n)_r} &\le& \left(\frac kn\right)^r\\ (1-\frac1k)(1-\frac2k)\dots(1-\frac{r-1}{k}) &\le& (1-\frac1n)(1-\frac2n)\dots(1-\frac{r-1}{n}). \end{eqnarray*} If we let $x=\frac kn$ and replace $\frac{(n-k)_p}{(n)_p}$ by $(1-x)^p$ and $\frac{(k)_q}{(n)_q}$ by $x^q$ we increase $g_{{\text{\em EXACT}}}$. Therefore $g_{{\text{\em EXACT}}} \le g_{{\text{\em APPROX}}}$ which proves Lemma 4.3. {\bf Proposition 4.4}\quad For all real $x$ ($0\le x\le 1$) $$ g_{{\text{\em APP}}}=\frac{x^{q-1}(1-x)^{p-1}(q(1-x)+px)}{q\cdot x^{q-1}+p(1-x)^{p-1}} \le \alpha^q $$ {\bf Lemma 4.4}\quad Proposition 4.4 $\implies$ Proposition 4.3. {\bf Proof}\quad W.l.o.g. we set $t_2 = 1$ since $g_{{\text{\em APPROX}}}$ is homogeneous in $t_1,t_2$. Take the derivative of $g_{{\text{\em APPROX}}}$ with respect to $x$, set it to zero and solve for $t_1$: $$t_1 = \frac qp\frac{x^{q-1}}{(1-x)^{p-1}}$$ If we substitute for $t_1$ in $g_{{\text{\em APPROX}}}$ we get $g_{APP}$. Note that the second derivative of $g_{{\text{\em APPROX}}}$ with respect to $x$ is $$t_1\cdot p \cdot (p-1)(1-x)^{p-2} + t_2\cdot q \cdot (q-1)x^{q - 2},$$ which is positive for any $x$ ($01$ and $t_1\neq 0$ or $q >1$ and $t_2 \neq 0$. {\bf Proof of Proposition 4.4}\quad We show first that the derivative of $g_{APP} (x)$ is zero in $(0,1)$ iff $x$ satisfies $(1-x)^p = x^q$. Let $A = x^q$, $B = (1-x)^p$. Then $$ g_{APP} (x) = \frac{A'B-AB'}{A'-B'} $$ The numerator of the derivative of $g_{APP} (x)$ is $$(A''B' - A'B'')(A-B).$$ The first factor \begin{eqnarray*} A''B' -A'B'' &=& -pq(q-1)x^{q-2}(1-x)^{p-1} - qp(p-1)x^{q-1}(1-x)^{p-2}\\ &=& x^{q -2}(1-x)^{p -2}( - (q -1)(1-x) - (p -1)x) \end{eqnarray*} has no zeros in $(0,1)$. Since $(1-x)^p = x^q$ has only one solution $\alpha$ in $(0,1)$ the rational function $g_{APP} (x)$ has one extremal point in $(0,1)$ with value $g_{APP} (\alpha) = \alpha^q$. Since $g_{APP} (0) = g_{APP} (1) = 0$ the function $g_{APP} (x)$ is maximal for $x = \alpha$. The proof of Proposition 4.4 uses differentiation. We give now a different proof which does not use differentiation and which provides further insight into the problem. {\bf Proposition 4.5}\quad For all real $x,\beta$ ($0 \le x,\beta \le 1$) $$ g_2(x,\beta)= x^q [(1-x)^p(px-qx+q)+(1-\beta)^pq(x-1)]- (1-x)^p\beta^q\cdot p\cdot x\le 0 $$ {\bf Lemma 4.5}\quad Proposition 4.5 $\implies$ Proposition 4.4. {\bf Proof}\quad Multiply both sides of $g_{APP} (x) \le \alpha^q$ by the denominator of $g_{APP} (x)$ and shift all terms to the left of the inequality sign. The resulting inequality is $g_2(x ,\beta) \le 0$ if we make liberal use of $(1-\alpha)^p = \alpha^q$ (a crucial point) and if we substitute $\beta$ for $\alpha$. {\bf Proof of Proposition 4.5}\quad So far a proof of Proposition 4.5 was obtained only for special cases. \begin{enumerate} \item[I)] $p=1,q \ge 1$. Note that $$ g_2(x,\beta)= (x-\beta)^2 \sum_{i=1}^{q-1} x^{q-i-1}(i-q)\beta^{i-1} $$ Hence $g_2(x,\beta)$ is non-positive for $0\le x,\beta\le 1$. {\bf Example:} ($p =1$) \\ $g_2(x ,\beta)$ is proportional to (the deleted factor has a positive sign)\\ $-(x-\beta)^2$ for $q=2$. \\ $-(x -\beta)^2(2x +\beta)$ for $q =3$.\\ $ -(x -\beta)^2(3x^2+2x \alpha+ \alpha^2)$ for $q =3$. \item[II)] $p=2$.\\ $g_2(x ,\beta)$ is proportional to (the deleted factor has a positive sign) \\ $(x -\beta)^2(x (x -4) + 2\beta(x -1))$ for $q =3$.\\ $ (x -\beta)^2(x^2(x -3) + 2\beta x (x -1) + \beta^2(x - 1))$ for $q=4$.\\ $ (x -\beta)^2(x^3(3x - 8) + 6\beta x^2(x - 1) + 4\beta^2x(x - 1) + 2\beta^3(x-l))$ for $q =5$. \end{enumerate} Unfortunately this technique does not generalize for $p \ge 3$ but it is conjectured that Proposition 4.5 holds in general. The formulas obtained by the alternate proof method have interesting applications. The following theorem allows us to predict which fraction of the clauses can be satisfied in every formula if the index of the maximal {\em mean}$_k (S)$ is fixed. {\bf Theorem 4.6}\quad Let $S$ be a formula in $ F' (1,q)$ ($q >1$) for which $$ \max_{0\le k\le n} {\text{\em mean}}_k(S) ={\text{\em mean}}_0(S). $$ Then assignment $J_{ALL\ 0}$, which assigns false to all variables satisfies all clauses. In general, if $\max\limits_{0\le k\le n}${\em mean}$_k (S) =$ {\em mean}$_{k'} (S)$ then the assignment which assigns true to $k'$ variables satisfies at least the fraction $$ 1-\alpha^q- \frac{ (\frac{k'}n-\alpha)^2 \sum\limits_{i=1}^{q-1} (i-q) \alpha^{i-1}(\frac{k'}n)^{q-i-1} }{ q\cdot(\frac{k'}n)^{q-1}+1 } $$ of the clauses. {\bf Proof}\quad Consider $g_{APP}(x)-\alpha^q$ for $p=1$ (after multiplying with $q\cdot x^{q-i}+1$): $$ qx^{q-1}(1-x) + x^q - \alpha^q\cdot (q\cdot x^{q-1}+1) = (x-\alpha)^2 \sum_{i=1}^{q-1} x^{q-i-1}(i-q)\alpha^{i-1}. $$ Let $$ h(x) = \frac{ (x-\alpha)^2 \sum\limits_{i=1}^{q-1} x^{q-i-1}(i-q)\alpha^{i-1} }{ q\cdot x^{q-1}+1 } $$ Now, $$ h(0)=\alpha^2(-1\cdot \alpha^{q-2})=-\alpha^q. $$ {\bf Proof of Theorem 4.1(ii)}\quad Algorithm MAXMEAN* guarantees to satisfy the fraction $\tau_{p ,q}$ in polynomial time. {\bf Proof of Theorem 4.1(iii)}\quad The fact that the satisfiability problem for formulas in $F (p ,q)$ is NP-complete follows from a general result of [Schaefer (1978)]. Then the proof can be adapted from [Lieberherr/Specker (1981)]. {\bf Extensions}\\ The technique used to prove Theorem 4.1(i) is suitable to determine $\tau_\psi$, for other sets $\psi$ which contain only two relations. The fraction of satisfied clauses in a symmetric formula which contains $t_1$ clauses with the first relation and $t_2$ clauses with the second relation is given by (in approximated form) $$ h_1(x,t_1,t_2) = \frac{t_1R_1(x)+t_2R_2(x)}{t_1+t_2}, $$ where $R_1$ and $R_2$ are polynomials which depend on the two relations. W.l.o.g.~$t_2 = 1$. If we take the derivative of $h_1$ with respect to $x$ and solve for $t_1$ we get $$t_1 = \frac{- R_2' ( x )}{ R_1' (x)}.$$ Substituting in $h_1$ we get $$ h_2(x)=\frac{R_1'(x)R_2(x)-R_1(x)R_2'(x)}{R_1'(x)-R_2'(x)}. $$ The numerator of the derivative of $h_2(x)$ is given by $$(R_1(x)-R_2(x))(R_1'' (x)R_2' (x)-R_1' (x)R_2'' (x)).$$ If the second factor has no zeros in $(0,1)$ then the fraction $R_1(\alpha)$ can always be satisfied, where $\alpha$ is the solution of $R_1(x) = R_2(x)$ in $(0,1)$ which is the global minimum of $h_2$. \section{Partial Solution of the 3-Satisfiability Problem} In [Lieberherr/Specker (1981)] the following problem was left open. A formula $S$ of the propositional calculus in conjunctive normal form (cnf) is said to be {\em 3-satisfiable}, if any triple of clauses is satisfiable. We find a lower bound on the fraction $\tau_3$ of the clauses which can always be satisfied in a 3-satisfiable formula by showing in the following that $\tau_3 > 2/3$. Unfortunately we have not been able to determine $\tau_3$ exactly. The motivation for studying $k $-{\em satisfiable} formulas is the relationship to polynomial approximation schemes for satisfiability [Lieberherr/Specker (1981), Huang/Lieberherr (1981)]. The problem with 3-satisfiable formulas is that they are not closed under symmetrization. If we take a 3-satisfiable formula $S$ and symmetrize it with the full permutation group then the symmetrized formula is in general not 3-satisfiable. To show that $\tau_3 > 2/3$ we construct a class $RED_1$ of formulas so that \begin{enumerate} \item[1.] $RED_1$ contains all 3-satisfiable formulas (but some are not 3-satisfiable) \item[2.] in any formula in $RED_1$ at least the fraction 2/3 of the clauses can be satisfied. \end{enumerate} Consider any 3-satisfiable formula $S$. Without loss of generality we assume that clauses of length 1 only contain positive literals (this can be enforced by renamings). Now we partition the variables into two classes. The first class contains only variables which occur in clauses of length 1. The second class contains all other variables. A clause is said to be type $T_{ij}^q$ if its $j$ variables are in class $q$ and $i$ of them are positive. A clause is said to be of type $T_{i_1j_1i_2j_2}^{qr}$ if it contains $j_1$ variables of class $q$ and $j_2$ variables of class $r$ and if $i_1$ of the $j_1$ variables are positive and $i_2$ of the $j_2$ variabIes are positive. {\bf Definition}\quad $RED_1$ is the following subset of cnfs: The variables are partitioned into 2 classes ($A$-variables and $B$-variables) and only the following clause types occur: $$T_{11}^1, T_{03}^1, T_{01\,11}^{12}, T_{01\,01}^{12}, T_{02}^2 , T_{12}^2, T_{22}^2.$$ This definition is of interest since for proving that $\tau_3 > 2/3$ it is sufficient to minimize among the formulas in $RED_1$. {\bf Theorem 5.1}\quad (i) In any 3-satisfiable cnf at least the fraction 2/3 of the clauses can be satisfied. (ii) There is a polynomial algorithm to find such an assignment. {\bf Proposition 5.2}\quad In any cnf in $RED_1$ at least the fraction 2/3 of the clauses can be satisfied. {\bf Lemma 5.2}\quad Proposition 5.2 $\implies$ Theorem 5.1(i). {\bf Proof}\quad Any 3-satisfiable cnf is easily reduced to a formula in $RED_1$ by deleting literals. Deleting literals makes a formula harder for satisfying many clauses. {\bf Definition}\quad Let $RED_2$ be the subset of cnfs of $RED_1$ which do not contain clauses with types $T_{02}^2, T_{12}^2$ and $T_{22}^2$. {\bf Proposition 5.3}\quad In any cnf in $RED_2$ at least the fraction 2/3 of the clauses can be satisfied. {\bf Lemma 5.3}\quad Proposition 5.3 $\implies$ Proposition 5.2. {\bf Proof}\quad In a cnf containing clauses of exactly length 2 at least the fraction 3/4 of the clauses can be satisfied (a random assignment satisfies 3/4). Therefore deleting clauses of the above three types does not make it easier to satisfy many clauses. We prove now Proposition 5.3 by a sequence of further reductions. Let $S$ be a formula in $RED_2$ which contains $t_1$ clauses of type $T_{11}^1$, $t_2$ clauses of type $T_{01\,11}^{12}$, $t_3$ clauses of type $T_{03}^{1}$ and $t_4$ clauses of type $T_{01\,11}^{12}$. The worst-case formulas (regarding the fraction of satisfiable clauses) in $RED_2$ are those which are symmetric in the $A$-variables and $B$-variables. Among those formulas the formulas with $t_2=t_4$ are hardest. In a formula in $RED_2$ with $t_2 = t_4$ the fraction $$ 1-\frac{ \frac{t_1}{n}(n-k) +\frac{t_2}{n}k + \frac{t_3}{\binom n3}\binom k3 }{ t_1+2t_2+t_3 } $$ of the clauses are satisfied if $k$ of the $n$ $A$-variables are set to 1. Therefore, we have to show {\bf Proposition 5.4}\quad For all integers $n$ and for all positive integers $t_1,t_2,t_3$ there is an integer $k$ ($0\le k \le n$) such that $$ \frac{ \frac{t_1}{n}(n-k) +\frac{t_2}{n}k + \frac{t_3}{(n)_3}(k)_3 }{ t_1+2t_2+t_3 }\le \frac13. $$ {\bf Lemma 5.4}\quad Proposition 5.4 $\implies$ Proposition 5.3. {\bf Proof}\quad Given above. {\bf Proposition 5.5}\quad For all integers $n$ and for all positive integers $t_1,t_2,t_3$ there is an integer $k$ ($0\le k\le n$) such that $$ w_1= \frac{ \frac{t_1}{n}(n-k) +\frac{t_2}{n}k + \frac{t_3}{n^3}k^3 }{ t_1+2t_2+t_3 } \le\frac13. $$ {\bf Lemma 5.5}\quad Proposition 5.5 $\implies$ Proposition 5.4. {\bf Proof}\quad Observe that $\frac{(k)_r}{(n)_r}\le \frac{k^r}{n^r}$ if $k \le n$. {\bf Proposition 5.6}\quad For all $x$ ($0 \le x \le 1$) and all positive integers $t_3$ $$ w_2= \frac{1-2t_3x^3}{3+t_3(1-6x^2)} \le\frac13. $$ {\bf Lemma 5.6}\quad Proposition 5.6 $\implies$ Proposition 5.5. {\bf Proof}\quad W.l.o.g.~let $t_1 = 1$ and substitute $x$ for $\frac kn$ in $w_1$. Take the derivative of $w_1$ with respect to $x$, set it to zero and solve for $t_2$: $$t_2=1- 3t_3x^2.$$ By substituting $1- 3t_3x^2$ for $t_2$ in $w_1$ we get $w_2$. Proposition 5.6 is easily proven directly by case analysis. \begin{thebibliography}{ppp} \bibitem[Huang/Lieberherr (1981)]{a} M.A. Huang and K.J. Lieberherr: Towards an approximation scheme for generalized satisfiability. Report 292, Dep. of EECS, Princeton University, 1981. \bibitem[Lieberherr/Specker (1981)]{b} K.J. Lieberherr and E. Specker: Complexity of partial satisfaction. Journal of the ACM, vol. 28, no. 2, pp. 411--421, 1981. \bibitem[Lieberherr (1982)]{c} K.J. Lieberherr: Algorithmic extremal problems in combinatorial optimization. Journal of Algorithms, vol. 3, pp. 225--244, 1982. \bibitem[Schaefer (1978)]{d} T. Schaefer: The complexity of satisfiability problems. Proc. 10th Annual ACM Symposium on Theory of Computing, pp. 216--226, 1978. \end{thebibliography} {\bf Author address:} Northeastern University\\ ATTN: Karl J. Lieberherr\\ College of Computer and Information Science MS WVH-202 \\ 360 Avenue of the Arts\\ Boston, MA 02115-5000\\ USA \end{document}