  In the maximum constraint satisfaction problem (Max CSP), one is given a
finite collection of (possibly weighted) constraints on overlapping sets of
variables, and the goal is to assign values from a given domain to the
variables so as to maximize the number (or the total weight, for the weighted
case) of satisfied constraints. This problem is NP-hard in general, and,
therefore, it is natural to study how restricting the allowed types of
constraints affects the approximability of the problem. It is known that every
Boolean (that is, two-valued) Max CSP problem with a finite set of allowed
constraint types is either solvable exactly in polynomial time or else
APX-complete (and hence can have no polynomial time approximation scheme unless
P=NP. It has been an open problem for several years whether this result can be
extended to non-Boolean Max CSP, which is much more difficult to analyze than
the Boolean case. In this paper, we make the first step in this direction by
establishing this result for Max CSP over a three-element domain. Moreover, we
present a simple description of all polynomial-time solvable cases of our
problem. This description uses the well-known algebraic combinatorial property
of supermodularity. We also show that every hard three-valued Max CSP problem
contains, in a certain specified sense, one of the two basic hard Max CSP
problems which are the Maximum k-colourable subgraph problems for k=2,3.
