The use of coding theory in computational complexity
Joan Feigenbaum · Proceedings of symposia in applied mathematics · 1995
The interplay of coding theory and computational complexity theory is a rich source of results and problems. This article surveys three of the major themes in this area: ffl the use of codes to improve algorithmic efficiency ffl the theory of program testing and correcting, which is a complexity theoretic analogue of error detection and correction ffl the use of codes to obtain characterizations of traditional complexity classes such as NP and PSPACE; these new characterizations are in turn used to show that certain combinatorial optimization problems are as hard to approximate closely as they are to solve exactly. 1 Introduction Complexity theory is the study of efficient computation. Faced with a computational problem that can be modelled formally, a complexity theorist seeks first to find a solution that is provably efficient and, if such a solution is not found, to prove that none exists. Coding theory, which provides techniques for "robust representation" of information, is va...