We introduce a simple technique to obtain reductions
between optimization constraint satisfaction problems. The
technique uses the probabilistic method to reduce the size of
disjunctions. As a first application, we prove the
MAX NP-completeness of MAX 3SAT without using the PCP theorem
(thus solving an open ... more >>>