Immerman, Neil2007-04-232007-04-231980-02http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR80-410https://hdl.handle.net/1813/6250We 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}].$2040901 bytes578765 bytesapplication/pdfapplication/postscripten-UScomputer sciencetechnical reporttechnical report