eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/6506
Title:  Lower Bounds by KolmogorovComplexity 
Authors:  Li, Ming 
Keywords:  computer science technical report 
Issue Date:  Mar1985 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR85666 
Abstract:  Using Kolmogorovcomplexity, we obtain the following new lower bounds. For online 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 1way DFA ($k$DFA) can do string matching, we develop a set of techniques and show that 3DFA cannot do string matching, settling the case $k = 3$. Some other related lower bounds are also presented. 
URI:  http://hdl.handle.net/1813/6506 
Appears in Collections:  Computer Science Technical Reports

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