97-45: Some Pointed Questions Concerning Asymptotic Lower Bounds

DIMACS TR: 97-45

Some Pointed Questions Concerning Asymptotic Lower Bounds

Author: Eric Allender

ABSTRACT
This column was originally written to appear in the Bulletin of the EATCS. In this column, I survey some aspects of complexity theory that can hardly be considered ``recent''. Instead, I will focus on some fundamental truths relating complexity theory to practical computing. These truths deserve repeating, lest they become forgotten.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-45.ps.gz

DIMACS Home Page