We study the complexity of an infinite class of optimization satisfiability problems. Each problem is represented through a finite set, (S), of logical relations (generalizing the notion of clauses of bounded length). We prove the existence of a dichotomic classification for optimization satisfiability problems Max-Sat(S). We exhibit a particular infinite set of logical relations (\mathscr{L}), such that the following holds: If every relation in (S) is 0 -valid (respectively 1 -valid) or if every relation in (S) belongs to (\mathscr{L}), then (\operatorname{Max}-\operatorname{Sat}(S)) is solvable in polynomial time, otherwise it is MAX SNP-complete. Therefore, (\operatorname{Max}-\operatorname{Sat}(S)) either is in (P) or has some (\epsilon)-approximation algorithm with (\epsilon<1) although not a polynomial-time approximation scheme, unless (\mathrm{P}=\mathrm{NP}: \mathscr{L}=) (\left{\right.) Pos ({n}), Neg ({n}), Spider ({n, p, q}), Complete-Bipartite (\left.{n, p}: n, p, q \in N\right}), where (\operatorname{Pos}{n}\left(x{1}, \ldots, x_{n}\right) \equiv\left(x_{1} \wedge \cdots \wedge x_{n}\right)).
(\operatorname{Neg}{n}\left(x{1}, \ldots, x_{n}\right) \equiv\left(\neg x_{1} \wedge \cdots \wedge \neg x_{n}\right)).
Spider ({n, p, q}\left(x{1}, \ldots, x_{n}, y_{1}, \ldots, y_{p}, z_{1}, \ldots, z_{q}\right))
(\equiv \wedge_{i=1}^{n}\left(x_{i} \rightarrow y_{1}\right) \wedge \wedge_{i=1}^{p}\left(y_{1} \equiv y_{i}\right) \wedge \wedge_{i=1}^{q}\left(y_{1} \rightarrow z_{i}\right)), and
Complete-Bipartite ({n, p}\left(x{1}, \ldots, x_{n}, y_{1}, \ldots, y_{p}\right) \equiv \bigwedge_{i=1}^{n} \bigwedge_{j=1}^{p}\left(x_{i} \rightarrow y_{j}\right)).
c. 1995 Academic Press, Inc.