DocumentCode
2180730
Title
Length of predicate calculus formulas as a new complexity measure
Author
Immerman, Neil
fYear
1979
fDate
29-31 Oct. 1979
Firstpage
337
Lastpage
347
Abstract
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].
Keywords
Calculus; Clocks; Computer science; Extraterrestrial measurements; Length measurement; Logic; Size measurement; Testing; Time measurement; Turing machines;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1979., 20th Annual Symposium on
Conference_Location
San Juan, Puerto Rico
ISSN
0272-5428
Type
conf
DOI
10.1109/SFCS.1979.21
Filename
4568029
Link To Document