Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MAX NP:
Reports tagged with MAX NP:
TR97-039 | 11th September 1997
Pierluigi Crescenzi, Luca Trevisan

MAX NP-Completeness Made Easy

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 >>>




ISSN 1433-8092 | Imprint