Number of Quantifiers is Better than Number of Tape Cells
| dc.contributor.author | Immerman, Neil | en_US |
| dc.date.accessioned | 2007-04-23T16:38:35Z | |
| dc.date.available | 2007-04-23T16:38:35Z | |
| dc.date.issued | 1980-02 | en_US |
| dc.description.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}].$ | en_US |
| dc.format.extent | 2040901 bytes | |
| dc.format.extent | 578765 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR80-410 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6250 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Number of Quantifiers is Better than Number of Tape Cells | en_US |
| dc.type | technical report | en_US |