Number of Quantifiers is Better than Number of Tape Cells

Abstract

We introduce a new complexity measure, $QN[f(n)]$, which clocks the size of sentences from predicate calculus needed to express a given property. Techniques from logic are used to prove sharp lower bounds in the measure. These results demonstrate space requirements for computations and may provide techniques for separating Time and Space complexity classes because we show that: $NSPACE [f(n)] \subseteq QN[f(n)^{2}/log(n)] \subseteq DSPACE[f(n)^{2}].$