Lower bounds on the size of sweeping automata
Michael Sipser · 1979
Establishing good lower bounds on the complexity of languages is an important area of current research in the theory of computation. However, despite much effort, fundamental questions such as P =? NP and L =? NL remain open. To resolve these questions it may be necessary to develop a deep combinatorial understanding of polynomial time or log space computations, possibly a formidable task.