Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with computationalcomplexity:
TR95-023 | 16th May 1995
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

On Syntactic versus Computational views of Approximability

We attempt to reconcile the two distinct views of approximation
classes: syntactic and computational.
Syntactic classes such as MAX SNP allow for clean complexity-theoretic
results and natural complete problems, while computational classes such
as APX allow us to work with problems whose approximability is
well-understood. Our results give a computational ... more >>>

ISSN 1433-8092 | Imprint