Answers are grounded in this paper and cite their sources.
We introduce a new complexity measure, QR[f(n)], which clocks the size of formulas 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 seperating Time and Space complexity classes because we show that: NSPACE[f(n)] ⊆ QR[(f(n))2/log(n)] ⊆ DSPACE[f(n)2].
No takes yet. Share an insight, caveat, or question.
Neil Immerman (1979) studied this question.