Number of quantifiers is better than number of tape cells
作者：
Highlights：
•
摘要
We introduce a new complexity measure, QN[f(n)], which measures the size of sentences from predicate calculus needed to express a given property. We show that: NSPACE[f(n)]⊆QN[(f(n))2/log n]⊆DSPACE[(f(n))2]. Fraisse-Ehrenfeucht games are used to prove sharp lower bounds in the measure.
论文关键词：
论文评审过程：Received 5 January 1981, Revised 15 January 1981, Available online 4 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(81)90039-8
