Accession Number:

ADA256729

Title:

Fixed Points in Spectral Complexity

Descriptive Note:

Research rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1992-10-01

Pagination or Media Count:

16.0

Abstract:

Spectral analysis has emerged as an exciting tool in complexity research. In some cases, the functions in a complexity class can be characterized by specifying a simple property of their Fourier spectra--even though their truth tables do not display such simple properties. In this paper, we demonstrate a fundamental limitation of this tool if a class of functions contains parity and is closed under some simple composition rules, then we can take the set of Fourier spectra of a subset of that class, close it under some simple projections, and obtain everything in the original class. Indeed, we can demonstrate this property for a general family of transforms, of which the parity-based Fourier transform is only one. If a class contains the basis function of such a transform, then no reduction in complexity is obtained when we shift from truth tables to spectra.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE