## Proceedings, Volume 9, Part 1994 |

### From inside the book

Results 1-3 of 31

Page 65

Thus, why should one be interested in sublogarithmic space complexity classes?

Let us use the shorthand Hog for the twice iterated logarithmic function n (-+ log2

log2 n . A deterministic or nondeterministic Turing machine (TM) that uses less

than Hog space can recognize regular languages only [SHL65, HoU169]. Since

there exist nonregular languages in DSpace(Mog ) the function Hog has turned

out to be the smallest non- trivial

...

Thus, why should one be interested in sublogarithmic space complexity classes?

Let us use the shorthand Hog for the twice iterated logarithmic function n (-+ log2

log2 n . A deterministic or nondeterministic Turing machine (TM) that uses less

than Hog space can recognize regular languages only [SHL65, HoU169]. Since

there exist nonregular languages in DSpace(Mog ) the function Hog has turned

out to be the smallest non- trivial

**space bound**, at least for deterministic and non-...

Page 66

If a complexity bound S is fully space-constructible for each input one could mark

in advance the number of available memory cells to prevent that this

acceptor M for L has at least one accepting computation that uses space at most

5(|jf |) we can easily achieve that all computation paths stay within this bound. For

sublogarithmic bounds, however, the following distinction becomes important.

Definition 2 ...

If a complexity bound S is fully space-constructible for each input one could mark

in advance the number of available memory cells to prevent that this

**space****bound**is exceeded. Thus assuming that for each string X in a language L anacceptor M for L has at least one accepting computation that uses space at most

5(|jf |) we can easily achieve that all computation paths stay within this bound. For

sublogarithmic bounds, however, the following distinction becomes important.

Definition 2 ...

Page 77

Combining Theorem 15 with the other upper and lower bounds on nonregular

context-free langugages the situation concerning

follows. The general upper

necessary and for some language this is also sufficient. Restricting to the

subclass of deterministic context- free languages, however, the lower

increases to A Alter ...

Combining Theorem 15 with the other upper and lower bounds on nonregular

context-free langugages the situation concerning

**space**complexity looks asfollows. The general upper

**bound**is DSpace(loga) and the best lower**bound**N**Space**(il(l\og )) , that means Hog is the minimal amount of nondeterministic**space**necessary and for some language this is also sufficient. Restricting to the

subclass of deterministic context- free languages, however, the lower

**bound**increases to A Alter ...

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Approximate Sets | 11 |

Polynomial Time TruthTable Reductions to PSelective Sets | 24 |

On the Query Complexity of Clique Size and Maximum Satisfiability | 31 |

Copyright | |

25 other sections not shown

### Other editions - View all

### Common terms and phrases

acceptance types algorithm assume binary Boolean Boolean circuit circuit collapses complete sets complexity classes Complexity Theory Computer Science configuration conjecture consider construction Corollary countable defined Definition denote deterministic DLOGTIME encoding exists exponential fan-in finite formula func function gate given graph guess hard hierarchy holds IEEE implies input head integer isomorphism leaf languages Lemma length live blocks logspace logspace reductions lower bound many-one many-one reduction martingale MAX3SAT NEXPTIME nodes nondeterministic Note NP-complete NP-hard O(logn optimal oracle oracle Turing machine output p-selective set P/poly path Player polynomial polynomial hierarchy polynomial-time predicate prob probabilistic Probabilistic Turing Machine probability Proc proof of Theorem proof systems Proposition protocol prove PSPACE PSPACE-hard recursive reductions representation class satisfying sequence simulate space bound strategy strings Structure in Complexity subset tape tion truth-table reducible Turing machine Ultrafilter unambiguous variables verifier weakly