DIMACS TR: 95-22

The Use of Coding Theory in Computational Complexity

Author: Joan Feigenbaum


The interplay of coding theory and computational complexity theory is a rich source of results and problems. We survey three of the major themes in this area:

1. the use of codes to improve algorithmic efficiency

2. the theory of program testing and correcting, which is a complexity theoretic analogue of error detection and correction

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

This article is based on a talk given at the Short Course on Coding Theory at the American Mathematical Society meeting in San Francisco, CA in January, 1995.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-22.ps.gz

DIMACS Home Page