\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<r)
$$
and therefore inductively
$$
f_{j+1,r} = \frac{j+1}{r-j} f_{j,r} = \frac{j+1}{r-j} \ 
\frac{j\cdot(j-1)\cdots1}{r(r-1)\cdots(r-j+1)}\cdot\frac1{r+1} = 
\frac1{\binom{r}{j+1}}.
$$

{\bf Lemma 3.3}\quad
Let
$$
\vec t = (t_0, t_1,\ldots , t_r)\qquad (\sum_{j=0}^r t_j=1)
$$
and let
$$
{\text{\em appmean}}_x(\vec t) =
\sum_{j=0}^r t_j\binom rj x^j (1-x)^{r-j}.
$$
Then there is $x_0$ ($0 \le x_0 \le 1$) such that
$$
{\text{\em appmean}}_{x_0}(\vec t)=\frac1{r+1}.
$$
{\bf Proof}\quad
Consider
\begin{eqnarray*}
\int_0^1 {\text{\em appmean}}_x(\vec t) dx &=&
\sum_{j=0}^r t_j\binom rj\int_0^1 x^j(1-x)^{r-j} dx\\
&=& \sum_{j=0}^r t_j \binom rj\frac1{\binom rj(r+1)}=\frac1{r+1}.
\end{eqnarray*}
The claim follows from the mean value theorem of calculus.

{\bf Lemma 3.4}
$$
\min_{\vec t} \max_{0\le x\le 1} {\text{\em appmean}}_x(\vec t)=
\max_{\vec t} \min_{0\le x\le 1} {\text{\em appmean}}_x(\vec t)=
\frac1{r+1}
$$
{\bf Proof}\quad
Let
$$
\vec b = \left(\frac1{r+1},\frac1{r+1},\ldots, \frac1{r+1}\right)\qquad{\text{$r+1$ dimensional}.}
$$
Then
$$
{\text{appmean}}_x(\vec b) = \frac1{r+1}\sum_{j=0}^r\binom rj x^j(1-x)^{r-j}=\frac1{r+1}
$$
Therefore
$$
\min_{\vec t}\max_{0\le x\le 1}{\text{\em appmean}}_x(\vec t)\le \frac1{r+1},
$$
since for $\vec t=\vec b$
only the fraction $\frac1{r+1}$ can be satisfied (independent of $x$).

Also
$$
\max_{\vec t}\min_x {\text{\em appmean}}_x(\vec t)\ge \frac1{r+1},
$$
since for
$\vec t = \vec b$ the minimal $x$ satisfies the fraction $\frac1{r+1}$.
On the other hand for any
$\vec t$ there is an $x_0$ such that
$$
{\text{\em appmean}}_{x_0}(\vec t) = \frac1{r+1}.
$$
Therefore
$$
\min_{\vec t}\max_{0\le x\le 1}{\text{\em appmean}}_x(\vec t)\ge \frac1{r+1},
$$
and
$$
\max_{\vec t}\min_{0\le x\le 1}{\text{\em appmean}}_x(\vec t)\le \frac1{r+1}.
$$
{\bf Proof of 3.1(ii) and 3.1(iii)}\quad
Algorithm MAXMEAN* guarantees to satisfy the fraction $\frac1{r+1}$
in polynomial time. It follows from a general result in [Schaefer (1978)] that the 
$\psi$-satisfiability problem is NP-complete (for the $\psi$ under discussion). Then (iii)
follows from Theorem 1.2 in [Lieberherr (1982)].

\section{Satisfiability}
Let $F (p ,q)$ be the following class of propositional formulas in conjunctive
normal form: Each clause in a formula in $F (p ,q)$ contains at least $p$ positive 
or $q$ negative literals ($p,q \ge 1$).

Let $\alpha$ be the solution of $(1-x)^p = x^q$
in $(0,1)$ and let
$\tau_{p,q}= 1 - \alpha^q$.

{\bf Theorem 4.1}
\begin{enumerate}
\item[(i)] In any formula in
$F (p ,q)$ the fraction
$\tau_{p ,q}$ of the clauses can be satisfied.
\item[(ii)] There is a polynomial algorithm MAXMEAN* which finds an assignment
satisfying at least the fraction $\tau_{p ,q}$ of the clauses in a formula in
$F(p,q)$.
\item[(iii)] For any rational $\tau' > \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$ ($0<x <1$), if $p >1$ 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}