OPTIMIZATION, APPROXIMATION, AND COMPLEXITY CLASSES

OPTIMIZATION, APPROXIMATION, AND COMPLEXITY CLASSES

1988 | Christos H. Papadimitriou, Mihalis Yannakakis
This paper introduces two complexity classes, MAX NP and MAX SNP, which are used to study the approximability of optimization problems. MAX SNP is a subclass of MAX NP, and both classes are defined based on the structure of optimization problems. The paper shows that problems in these classes can be approximated with bounded error, and that a number of common optimization problems are complete under a specific type of transformation called L-reduction. This implies that if a complete problem in MAX SNP can be approximated within a certain ratio, then all problems in MAX SNP can be approximated within that ratio. The results help explain the lack of progress in approximating a wide range of optimization problems. The paper discusses several optimization problems that are complete for MAX SNP, including MAX 3SAT, MAX 2SAT, MAX CUT, and others. It also shows that these problems can be approximated within a fixed ratio. The paper also addresses the difficulty of proving the existence of polynomial-time approximation schemes (PTAS) for these problems, and notes that most problem reductions do not preserve the approximability properties of the original problems. The paper concludes that MAX NP and MAX SNP are the first successful attempts to capture the intricacies of approximability in a complexity class. The results help reveal the common roots of the difficulty in understanding the limits of approximability for various optimization problems.This paper introduces two complexity classes, MAX NP and MAX SNP, which are used to study the approximability of optimization problems. MAX SNP is a subclass of MAX NP, and both classes are defined based on the structure of optimization problems. The paper shows that problems in these classes can be approximated with bounded error, and that a number of common optimization problems are complete under a specific type of transformation called L-reduction. This implies that if a complete problem in MAX SNP can be approximated within a certain ratio, then all problems in MAX SNP can be approximated within that ratio. The results help explain the lack of progress in approximating a wide range of optimization problems. The paper discusses several optimization problems that are complete for MAX SNP, including MAX 3SAT, MAX 2SAT, MAX CUT, and others. It also shows that these problems can be approximated within a fixed ratio. The paper also addresses the difficulty of proving the existence of polynomial-time approximation schemes (PTAS) for these problems, and notes that most problem reductions do not preserve the approximability properties of the original problems. The paper concludes that MAX NP and MAX SNP are the first successful attempts to capture the intricacies of approximability in a complexity class. The results help reveal the common roots of the difficulty in understanding the limits of approximability for various optimization problems.
Reach us at info@study.space
[slides and audio] Optimization%2C approximation%2C and complexity classes