Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Lower Bounds by Kolmogorov-Complexity
Authors: Li, Ming
Keywords: computer science
technical report
Issue Date: Mar-1985
Publisher: Cornell University
Abstract: Using Kolmogorov-complexity, we obtain the following new lower bounds. For on-line nondeterministic Turing machines, (1) simulating 2 pushdown stores by 1 tape requires $\Omega(n^{1.5} / logn)$ time; together with a newly proved $O( n^{1.5}\sqrt{logn})$ upper bound [L3], this basically settled the open problem 1 in [DGPR] for 1 tape vs. 2 pushdown case (the case of 1 tape vs. 2 tapes was basically settled by [M]); (2) simulating 1 queue by 1 tape requires $\Omega(n^{4/3} / logn)$ time; this brings us closer to a newly proved $O( n^{1.5}\sqrt{logn})$ upper bound [L3]; (3) simulating 2 tapes by 1 tape requires $\Omega(n^{2} / lognloglogn)$ time; this is a minor improvement of [M]'s $\Omega(n^{2} / log^{2}nloglogn)$ lower bound; it is also claimed (full proof contained in [L3]) that the actual languages used in [M] (also here) and [F] do not yield $\Omega(n^{2})$ lower bound. To cope with an open question of [GS] of whether a $k$-head 1-way DFA ($k$-DFA) can do string matching, we develop a set of techniques and show that 3-DFA cannot do string matching, settling the case $k = 3$. Some other related lower bounds are also presented.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
85-666.pdf2.19 MBAdobe PDFView/Open
85-666.ps438.21 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us